ABC202-F Integer Convex Hull

※5/27追記 タグ直しました。
https://atcoder.jp/contests/abc202/tasks/abc202_f
　所要時間は65分。コンテスト中の赤diffはFractal Shortest Pathに続き2問目。うれし～。でもその後Dで15分とかかけて結局E解き終わらなかったのアレですね。
　なんか解説見たけどいまいちよく分からなくて、もしかしたら自分の解法が解説と違うかもしれないなと思ったので、少し紹介。言語化が下手なので伝わりにくい可能性大。

## 凸多角形を数え上げる
　ある凸多角形の頂点を反時計回りに$P_1,P_2,\cdots P_n$とすると、ベクトル$\vec{P_1P_2},\vec{P_2P_3},\cdots$の偏角(正確にはベクトルを複素数と見做した時の偏角？)は、だんだん大きくなっていく。だから、この問題は頂点から頂点へのベクトル全てを偏角でソートして、そのベクトルを順々に追加していくことで、全ての凸多角形をまとめて扱いやすくなりそうだ。
　扱いやすいよう、頂点から頂点へのベクトルの偏角は$[-\pi,\pi)$の範囲で考える。(これは少なくともC++ではatan2を使って表現できるが、$y$座標が同じ頂点間のベクトルは、atan2だと$\pi$になってしまう場合があるので注意。)まず、全頂点を$y$座標が小さい順、$y$座標が同じものは$x$座標が小さい順にソートする。その後、全頂点間のベクトルを偏角順にソートする。

　$y$座標が最大のもののうち、$x$座標が最大のものを$P_m$とする。この点を頂点とする凸多角形は全て、$P_m$から偏角の小さい順に頂点間を結ぶベクトルを選んでいくことで出来上がる。要するに左下図の赤線や青線などを順番に取っていけば凸多角形になるということを言っている。考え方としてはギフト包装法に似ているかも？

<img width="300" alt="図1" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1183429/a1c73d3b-ab10-5bcf-097d-a062a2dcfe70.jpeg">　　　<img width="300" alt="図2" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1183429/c92781a6-794b-a552-e6c3-372bbfb3d241.jpeg">

　では、その面積はどう考えればいいのか。これは、右上の図のように$P_m$を含む三角形の足し合わせとして考える。三角形がつぶれてただの直線とか点とかになっているなら面積0と考える。
　三頂点が格子点にあるのでこの三角形の面積の2倍は整数になる。ということは、各三角形の面積の2倍が偶数になるか奇数になるかが分かれば、その足し合わせの凸多角形の面積の2倍が偶数か奇数かが分かり、その凸多角形の面積が整数になるかが分かるのだ。

　そこで、次のように配列を設定し更新する。まず、$ang$という変数を用意する。この変数は最初、$-\pi$としておく。これをだんだん増やしていき、$ang$がある値になった時、以下のような状態が実現されているようにする。

* 状態：偏角が$ang$以下のベクトルのみを使って、以上のように三角形を追加して頂点$P_m$から$P_i$まで来る方法のうち、そこまでの面積の2倍が「偶数」になるような通り数が$ev[i]$に保存されている。同様に面積の2倍が奇数の時は$od[i]$に保存されている。
<img width="400" alt="図1" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1183429/29fe1329-ce17-55bc-109b-8e5078ef0b76.jpeg">

　イメージとしては$ang$を$-\pi$から$\pi$までぐるぐる回す感じ。一番最初の更新のために$ev[m]$のみを1にしておく(面積0から足していくから)。そして、偏角が$ang$になるベクトルが見つかった時、以下のような更新作業を行う。

* 偏角が$ang$となるベクトルの始点を$P_a$とし、終点を$P_b$とする。$P_a,P_b,P_m$の3点が作る三角形の面積(点が一致するなら0)が偶数ならば、$ev[b]$+=$ev[a]$,$od[b]$+=$od[a]$を行う。奇数なら$ev[b]+=od[a]$,$od[b]$+=$ev[a]$を行う。
(偏角が一致するベクトルが複数あっても、それらは平行であり互いに干渉しないから心配は不要。同一直線上に3点がないことも事前に保証されている。それぞれを更新すれば良い。)

　これによって、更新後もしっかりと上に示した状態になることが確認できる。これを続けて、最終的には$ev[m]$に、面積の2倍が偶数になる(=面積が整数になる)凸多角形の通り数が保存されるという流れだ。ただし、$ev[m]$には一番最初に加えた1や、ある頂点に行って戻ってきただけの直線の通り数も含まれるから、これは後で除外しなければならない。

　ここまでの作業により、$P_m$を頂点に含む凸多角形のうち、面積が整数になるものの通り数が分かった。次は$P_m$を使わないものを考えるから、$P_m$を消して最大の座標を選び直し、同じ作業を行う。この作業がしやすいように、事前にソートしておけばいい。これを繰り返すと、全ての凸多角形について、面積が整数になるものが何通りあるかが分かる。

## 凸包を数え上げる
　以上より、凸多角形のうち、面積が整数になるものの通り数が分かった。ここまでで45分くらいかかった。
　しかし、これだけでは不十分だ。なぜなら、求められているのは凸多角形の通り数ではなく、「凸包の面積が整数となる<b>頂点集合の数</b>」だからだ。ここまで示したものでは凸多角形の通り数しか数えられていないから、三角形$P_1P_2P_3$の内部に$P_4$があれば、$P_1,P_2,P_3$の凸包も、$P_1,P_2,P_3,P_4$の凸包も、まとめて1つとして数えられてしまうが、本当は分けて数えないといけない。

　これらを別々に数える必要がある。そこで、ある凸多角形$C$がある時、「頂点集合$S$であって、$S$の凸包が$C$になるようなもの」が何通りあるかを考える。これは$C$の内部(頂点含まず)にある点の個数を$x$として、$2^x$通りになる。例えば内部に2つの頂点があるなら部分集合の選び方は4通り考えられる。詳しい証明はしないが、感覚的に分かると思う。
<img width="200" alt="図4" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1183429/24ba091f-bd9f-2e02-658d-168b9e05cdb0.jpeg">
　「内部にある頂点の個数」の情報を含めるのは難しくない。先ほどのように三角形を順に組み合わせていくと、三角形の内部に点が$x$個あるごとに頂点集合の数は$2^x$倍になる。ならば、それぞれの更新の時に、追加する三角形の内部($P_a,P_b,P_m$の3点が作る三角形の内部)に何個の点があるかを数え、その数を$x$として$2^x$を掛けてしまえばいいのだ。三角形の内部の点の個数は、事前に全ての3頂点組からなる三角形について、その内部にある頂点の個数が何個か数えておけば良い。これで、問題が解ける。


## まとめ
　ざっくりと以下のような感じである。細かい数えすぎを省くなどの作業は書かない。

* 全点を{$Y_i,X_i$}としてソートする。$O(N\log{N})$
* 全点間のベクトルを偏角でソートする。$O(N^2\log{N})$
* 全ての3点の組について、その点が作る三角形の内部に何個の点があるかを事前に数える。後述するが僕は$O(N^4)$で行った。
* ソートした状態で、Yが最大のもののうちXが最大のものを選んで$P_m$とする。$ang$という変数を用意し、$ang$を増やしながら次のような更新作業を行う。
    * 偏角が$ang$となるベクトルの始点を$P_a$、終点を$P_b$とする。$P_a,P_b,P_m$の3点が作る三角形について、内部にある点の数を$x$とし、面積(点が一致するなら0)が偶数ならば、$ev[b]$+=$ev[a]\times 2^x$,$od[b]$+=$od[a]\times 2^x$を行う。奇数なら$ev[b]$+=$od[a]\times 2^x$,$od[b]$+=$ev[a]\times 2^x$を行う。更新回数は辺の数だけあるから、$O(N^2)$

* $P_m$を消して上の作業を行う。その後同様に、$Y$の値が大きいものから、$Y$が同じなら$X$の値が同じなら大きいものから、$P_m$として上の作業を行い、$P_m$を消す。$O(N)$ステップあるから、各ステップの計算量と合わせて$O(N^3)$である。

結局、計算量は$O(N^4)$となる。実装は https://atcoder.jp/contests/abc202/submissions/22826752

<details><summary>三角形の内部の点の数を数える奴</summary>
　どうせ3点間の面積を求める部分は実装する必要があるので、内部にあるか否かの判定も面積を使ってしまおう。
　$P_p,P_q,P_r$を固定すると、$P_i$が内部にあるなら三角形の面積について下の等式が成り立つ。内部にないなら成り立たない。
$\triangle{P_pP_qP_i}+\triangle{P_pP_iP_r}+\triangle{P_iP_qP_r}=\triangle{P_pP_qP_r}$
　だから、$p,q,r$の三重ループの中で、$i$の四重目のループを回してカウントすればOK。
</details>

## 感想
　ABCの幾何楽しい！！！
　分かりやすく説明するのって難しいね。