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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

幾何コンテスト C:泥棒

突然の幾何コンテスト。
幾何ライブラリを前々から作るべきだと思っていたので軽い気持ちで解き始めたら痛い目を見ました。

- 問題概要

http://geocon2013.contest.atcoder.jp/submissions/363487C: 泥棒 - 幾何コンテスト2013 | AtCoder

泥棒が(0,0)のアジトにすんでいます。
1 \le x,y \le 10^8のとき、
1.i日後に泥棒が座標(x,y)の民家に盗みに行く
2.役人によって座標(x,y)に監視所が建てられる。
のいずれかがi日後に行われます。
泥棒は二つの監視所によって結ばれた直線を通過することができません。
1のとき、盗みをすることができるかどうかを答えなさい。
1の発生回数をN,2の発生回数をMとすると、N,Mは1\le N,M \le 10^5を満たします。

- 解法

泥棒が盗みを行うとき、民家にたどり着けるかどうかはi日時点での監視所によって構成される凸包内に民家があるかどうかによって決まります。
x,yともに1以上なのでアジトが囲まれることは絶対にないので、民家が囲まれていなければセーフなのです。
監視所の座標を保存しておき、盗みの度に凸包を求めても良いのですがこの方針だとO(NM \log\ M)となり、TLEとなります。
また、民家が凸包内にあるかの判定もo(NM)で行わなければいけません。スモールオーです。
後者の問題は凸多角形内部の点をとり、その点から見てどの二頂点間に民家があるかを二分探索で求めれば解決します。
問題は前者なのですが、凸包は部分的に更新することが可能です。
1.凸多角形内外判定のアルゴリズムと同様に内部の点から見てどの二頂点間に追加する点が存在するかを調べる。
2.内外判定を行う。凸多角形内部ならば点は追加しない。
3.1で発見した二頂点の間に点を追加し、隣接辺がCCWになるまで隣接点の削除を行う。
この動作を行うことにより凸包の部分的な更新が可能です。動的凸包と呼ばれるアルゴリズムだそうです。
問題は頂点の削除を行っている点です。配列を用いるとeraseにO(N)かかってしまいます。
しかしlistを使って実装すると内外判定の二分探索が不可能となってしまいます。
ここで登場するのが平衡二分探索木です。ただしi番目に小さい要素を取り出すことのできる仕組みが必要となります。
残念ながらsetやmapにはその機能が存在しないためSTLに頼ることはできません。
そこで、このページのAVL木を使わせていただきました。
http://www.prefield.com/algorithm/container/avl_tree.html
AVL木は子ノードの大きさを利用して平衡を保つ二分探索木ですのでi番目に小さい値の取得が容易に実装できます。
これに添え字演算子オーバーロードして使うと\log nで探索、削除、挿入が可能な配列の完成です。(あくまで二分探索木です)
挿入はdouble型の優先度を使って強引にねじこみました。
これを用いると要素の追加回数の合計はO(M\log M)、削除回数の合計もO(M\log M)
二分探索を行う回数がO((N+M) \log M)です。ただし、二分探索を行うときにAVL木へのアクセスを行っていますので全体の計算量は(N+M) (\log M)^2となります。
結構ギリギリなので定数倍部分を大きくしすぎるとTLEとなります。