ABC 019 D 一刀両断

atcoder.jp

問題概要

ある多角形の全ての頂点の座標が与えられる.
二点の座標が与えられその点を結んだ時に多角形を幾つの図形に分割するかを求める

解法

多角形を考えるのは難しいので多角形の辺と分割する直線の交わる本数を求めることで、幾つの図形に分割するかがわかる.

直線の交わり判定

ax , ay , bx , by : 図形を切断する直線の座標
px , py , qx , qy : 対象としている多角形の線分の2点の座標 

public static boolean Check(int px, int py, int qx, int qy) {

        long t1 = ((py - ay) * (bx - ax) - (px - ax) * (by - ay));
        long t2 = ((qy - ay) * (bx - ax) - (qx - ax) * (by - ay));

        long t3 = ((ay - py) * (qx - px) - (ax - px) * (qy - py));
        long t4 = ((by - py) * (qx - px) - (bx - px) * (qy - py));
        return t1 * t2 < 0 && t3 * t4 < 0;
    }

コメント

今回の問題ではCheck()の関数で扱う変数のかたをint型にしたらWAになってしまった.long型にしたら見事ACすることができました.
座標は10³の時 t1 は 10⁶ t2 も 10⁶ で t1 * t2 で 10¹² まで上がってしまうため,long型にする必要があった.

参考

• 直線の交わり