cgl_3_c 内積 外積 aoj 点の多角形の内包判定

CGL_3_C 点の多角形の内包判定

CGL_3_C 点の多角形の内包判定
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C

点が多角形に内包されるか、されないかまたは多角形の辺上にあるかを判定する問題.

解説

詳しいアルゴリズムは以下を参照.

多角形の点内包判定アルゴリズム

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MAX_N 101
#define MAX_Q 1001

Int N, Q;
Vector2 polygon[MAX_N];
Vector2 point;

Int contains(Vector2 &point) {
  bool in = false;
  loop(n,0,N) {
    Vector2 a = polygon[n] - point;
    Vector2 b = polygon[(n+1) % N] - point;
    if (fabs(a.cross(b)) < EPS && a.dot(b) < EPS) return 1;
    if (a.y > b.y) swap(a, b);
    if (a.y < EPS && b.y > EPS && a.cross(b) > EPS) in = !in;
  }

  return in ? 2 : 0;
}

void input() {
  cin >> N;
  loop(n,0,N) cin >> polygon[n];
  cin >> Q;
  while (cin >> point) {
    cout << contains(point) << endl;
  }
}

int main() {
  cout.precision(15);
  input();
}