Problems
Point and Polygon
Point and Polygon
How do programmers fix a light bulb?
They don't do it, it's a hardware problem!
Given a simple convex polygon and a point. Determine if the point is inside, on the border or outside the polygon.
Input
Contains several test cases. Each test case starts with the number of vertices n (n ≤ 1000) of the polygon, followed by n pairs of integers (x, y) (-1000 ≤ x, y ≤ 1000) representing the coordinates of polygon vertices in counter-clockwise order. Next line has two integers - the coordinates of the given point. The input terminates with the line that contains one 0.
Output
For each test case, print "INSIDE" if the point is inside the polygon, "**ON BORDER**" if the point lies on a border, or "OUTSIDE" if the point is outside the polygon.
Input example #1
4 4 0 4 4 0 4 0 0 2 2 3 0 0 2 0 1 1 -2 -2 0
Output example #1
INSIDE OUTSIDE