[問題案] Incremental Convex Hull

[maspypy]

問題名: Incremental Convex Hull

問題概要

はじめ $S$ は空集合である。 $Q$ 回次を行え。

• 0 x y： $S$ に点 $(x,y)$ を追加する
• 1 x y： $(x,y)$ が $conv(S)$ の内部に含まれるか、境界上であるか、外部にあるかを答える
• 2：現在の凸包の面積の 2 倍を出力する

制約

$Q\leq 5\cdot 10^5$ 座標は $\pm 10^9$ クエリ 1 の点は distinct

---

動的な凸包の管理としては https://judge.yosupo.jp/problem/convex_layers もあるのだが、大変すぎる。 実用としても Incremental 版が欲しい。

出題： https://atcoder.jp/contests/geocon2013/tasks/geocon2013_c https://atcoder.jp/contests/utpc2020/tasks/utpc2020_m

[maspypy]

・https://judge.yosupo.jp/problem/convex_layers では座標が $10^6$ だが、特に理由がなければ $10^9$ でよいかなと思う。 ・$N=0$ で $Q$ だけにしても良いかも。 ・出力させるものが何か良いのかは分からない。「点追加せよ / 頂点の個数と面積を出力せよ」くらいの方が良いかも。 ・Incremental な凸包と Incremental な CHT（Line Add Get Min）は実質一緒という説もある。

[yosupo06]

そういえば凸包の頂点数がO((座標)^(2/3))でboundされるみたいなのがあった気がするので、座標は10^9のほうが良さそうです

[SSRS-cp]

下位互換として、(Incremental ではない) 通常の凸包の問題もあるとよさそうだと思いました

[maspypy]

問題案をもうすこし具体的にしました。私が作業予定です。

[maspypy]

要望があるならついでに通常の凸包も作業してもよいです。

• 頂点を反時計回りに出力
• 最小頂点数（辺上に無駄な頂点が並ぶやつは消す）

くらいですか。

[maspypy]

揉めポイント：辺上の点も頂点数に含めるか否か。

https://judge.yosupo.jp/problem/convex_layers

では、凸包として「辺上の点」も含めている。（人々のライブラリではどちらが一般的だろうか）

[maspypy]

問題案を少しいじりました。 内外判定くらいできた方が良いと思ったので足しました。