多角形に対する点の内外判定
問題文 : 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); }