yukicoder No.325 マンハッタン距離2

問題文

http://yukicoder.me/problems/477

解法

求めるのは以下の領域の内部にある格子点の数。

この領域の頂点は格子点上にあるので、ピックの定理で格子点の数が計算できる。

ピックの定理
すべての頂点が格子点上にある単純多角形に対し、 多角形の面積を $S$ 、辺上にある格子点の個数を $b$ 、内部にある格子点の個数を $i$ としたとき次の等式が成り立つ。 $$ S = i + \frac12b - 1 $$

交差領域が求められれば、領域の面積と辺上にある格子点の個数を計算できる。 そこからピックの定理を使って内部にある格子点の個数が求められる。

問題なのは交差領域の求め方だけど、これは頑張るしかない。 凸多角形の交差を求めるライブラリがあれば貼るだけ。

実装

オーバーフローに注意。int128 を使うとか適当な素数 mod 上で計算するとか回避方法は色々ある。

yukicoder No.325 マンハッタン距離2

貼るだけで解きたかったけど交差なんて持ってなかった。