AOJ

# # Problem

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

Determine given points are contained in given polygon or not.

# # Explanation

See the link below for the detailed algorithm.

Polygon-Point Containment algorithm

# # Solution

#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();
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!