PHS - Geometry

Start

2018-05-18 18:59 UTC

PHS - Geometry

End

2018-05-25 18:59 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -306 days 20:48:39

Time elapsed

168:00:00

Time remaining

0:00:00

Problem D
Point in Polygon

Input

Input contains several test cases. Each test case begins with an integer $n$ ($3 \leq n \leq 1000$). Then follow the $n$ vertices of a simple polygon, one per line, each of the form $x\ y$. The points may be given in either clockwise or counterclockwise order. Then comes an integer $m$ ($m \leq 100$), giving the number of points to test, followed by $m$ lines, each containing a point in the same format as above. Coordinates are integers with absolute value bounded by 10000. The input is terminated by a case beginning with 0.

Output

For each test case, output $m$ lines, one for each point to test. The $i$:th output for a test case should be one of “in”, “out”, “on”, depending on whether the $i$:th test point lies inside, outside, or on the given polygon.

Sample Input 1 Sample Output 1
3
0 0
10 0
0 10
3
4 5
5 5
6 5
5
41 -6
-24 -74
-51 -6
73 17
-30 -34
2
-12 -26
39 -8
0
in
on
out
out
in