Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

ABC075-D Axis-Parallel Rectangle 解説

問題

D - Axis-Parallel Rectangle

解説

まず全ての点での全探索 O(N^4)を考えます, すると4つの点をそれぞれ4隅に置かない方が良いパターンで取り漏らしてしまうことが分かります, どうすれば対応ができるでしょうか.

これは実は簡単で2点を選んだ時に, それぞれがx軸とy軸に並行な辺に含まれると仮定してみましょう, すると新たにその辺どうしの交点も全探索の時に考慮しなければならないことが分かります.

ここまで来ればあとは実装するだけです, 正負とオーバーフローに注意して実装しましょう.

コード

Submission #1780748 - AtCoder Beginner Contest 075

感想

公式解説わかりにくい気がするんですがぼくだけですか.
全探索は全状態でのシミュレーションをするだけなんですが, 状態の取り漏らしに注意しないといけないですね.