ARC018-B 格子点と整数
解法が想定解と大きく異なったのでまとめておきます
問題
格子点上の点が N 個与えられる。
格子点を3つ選んでできる三角形の面積が正の整数であるような組がいくつあるか答えよ。
想定解
一点が原点(0, 0)上にある三角形の面積は |x_1 * y_2 - x_2 * y_1| / 2で求めることができるので、三角形を正規化したのち分子の偶奇で考える。
僕の解法
ピックの定理 を使う。
ピックの定理より、多角形の辺上にある格子点の数が偶数かどうかでその多角形の面積が整数かどうかが決まるため、辺上にある格子点の数を数える。
三角形上のある二点の x 座標の差を a , y 座標の差を b とすると、その二点を結んでできる辺上にある格子点の数は gcd(a, b)*1 + 1 個 になるので、3辺それぞれについて格子点の数を求めてやれば良いことがわかる。*2
しかし、この方法の場合 面積0 == 3点が直線上に位置する場合でも数えてしまうので、3点が直線上に並ぶ場合はあらかじめ辺の比などを使って除外しておく。
