Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

多角形に対する点の内外判定

問題文 : Polygon-Point Containment


解法 : 符号付き角度を足しあわせて, $\pm 2\pi$ (多角形方向による) であれば内包, ccw で返上なら返上, それ以外なら 外, と判定できる.

ローカルではテストケースは通るがAOJ ではWA になってしまいます...

コード :

int main()
{
    int n, q;
     
    scanf("%d", &n);
    Polygon p(n);
    for (int i = 0; i < n; i++){
        scanf("%lf %lf", &p[i].x, &p[i].y);
    }
     
    scanf("%d", &q);
    for (int i = 0; i < q; i++){
        Point t;
        scanf("%lf %lf", &t.x, &t.y);
         
        int state = 0;
        double fsum = 0;
        for (int j = 0; j < n; j++){
            Point next = p[(j + 1) % n];
            if (ccw(p[j], next, t) == 0) state = 1;
			else {
				assert(neq(abs(next - t), 0));
				assert(neq(abs(p[j] - t), 0));
				double th = acos(getCos(p[j] - t, next - t)) * ccw(p[j], t, next);
				fsum += th;
			}
        }
		printf("%d\n", state ? state : 2 * geq(abs(fsum), 2));
    }
     
    return (0);
}