読者です 読者をやめる 読者になる 読者になる

2009 Territory

みんなO(N log N)で解いているらしいですが工夫してひたすら実装してメモリ削るとBFSするだけで解けますとか言ってる人がいますが、O(N log N)で解きました。
基本的な方針は、軌跡を適当に処理し、左上の点から右手法を使うと図形の外側が得られます。
問題は面積の求め方ですが、これも実は単純で、先ほどの図形の東西方向の辺だけに注目するとあとは自明です。