CodeChef June Challenge 2016: Misha and Geometry
https://www.codechef.com/JUNE16/problems/MGCHGEOM
問題
以下の 2 種類のクエリが与えられる。
- 点(x, y) を追加する
- 点(x, y) を削除する
クエリを順に処理し、処理するたびに凸包の面積を出力せよ。
- クエリ数の合計は 105 以下
やったこと
- 点の追加だけなら全体で O(n) だが、点の削除が絡むとそうはいかない。
- 「動的凸法」で検索すると、いい感じのスライドを発見。
http://www.slideshare.net/naotomizuno10/geocon-29221605
- 削除も O(log2 n) でできるらしい。
- Overmars & van Leeuwen, 1981 で検索。次の pdf を発見。
- 詳細は分からないが、凸包の分割統治をセグメント木に乗せればうまくいくということだろうか。
- 永続使えばできそう。
- merge と revert を作ればいい。
- これ永続必要ない…。
- 凸包を切ったり繋いだりするので、凸包は平衡二分探索木で表現するのが良さそう。
- revert は凸包を切るだけなので、難しいのは merge。
- 凸包のマージには、凸多角形の共通接線を求めるアルゴリズムが必要。
- 点から凸多角形への接線は二分探索により O(log n)。
- 点から凸多角形への接線を反復適用することで、凸多角形の共通接線は定数×O(log n)？
- 凸包は平衡二分探索木で管理しているのだから、接線の二分探索は可能。
- 葉にだけデータを乗せたほうが二分探索しやすそう。
- merge/split が高速にできて、葉にだけデータを持たせるのなら赤黒木？
スクロールを多用しすぎてマウスホイールの調子が悪くなった。
