Hide

Problem F
Point in Polygon

Input

Input contains several test cases. Each test case begins with an integer n (3n1000). 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 (m100), 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
Hide

Please log in to submit a solution to this problem

Log in