Inside, Outside, or On the Fence

Difficulty: 1900 6000 ms 128 MB

geometry

Given a simple polygon and Q query points, classify each point as INSIDE, OUTSIDE, or BORDER.

Input: the first line has N; the next N lines are the polygon vertices in order; then a line with Q; then Q query points x y.

Output: one line per query.

Constraints:

• 3 ≤ N ≤ 10³
• 1 ≤ Q ≤ 10³
• |coordinates| ≤ 10⁶

Sample Tests

4
0 0
4 0
4 4
0 4
3
2 2
5 5
0 2

INSIDE
OUTSIDE
BORDER

3
0 0
2 0
0 2
1
1 1

BORDER

Read the Editorial