AtCoder Beginner Contest 130 [ C - Rectangle Cutting ]をPythonで解く。構築問題(300点、🟫茶diff)
問題文読んで自分なりに考えてみたが、解説みたらシンプル過ぎで驚き。
解法
はまやんさんの解説より引用。
この問題はある種の構築問題である。
構築問題の典型テクとして「理論値の最大値を実はいつも達成可能」というのがある。
今回もそうで、小さい方の面積の最大値の理論値は、全体の面積の半分である。
これはある一点が与えられたら、対角線の交点をもう一点とする直線を作れば、二等分線が作れる。
そのため、1番目の答えは面積の半分を常に答えればいい。
なるほど、そうかー。
長方形の中の任意の一点は、かならず半分にできる点が引けると。
2番目の答えは、対角線の交点が与えられた点であれば、どんな直線でも二等分になるので、1。
与えられた点が、長方形の中心点かどうかを判定するだけ。
なるほどねー。
まぁ、説明されちゃえば、そうなのねって感じだけど自分でこれだけシンプルな考えに到達できるかって感じよねー
実装
解法がわかっちゃえば、この問題のソースコードはシンプル。
