Inside the Fence

A farmer's fence is a polygon given as a list polygon of corners, each an (x, y) tuple of integers, in order around the fence (clockwise or counter-clockwise; the fence closes from the last corner back to the first). The fence never crosses or touches itself, but it does not have to be convex.

Write locate_point(polygon, point) that returns:

• 'boundary' if point lies on the fence itself, corners included,
• 'inside' if it is strictly inside the field,
• 'outside' otherwise.

Examples

fence = [(0, 0), (6, 0), (6, 6), (3, 3), (0, 6)]
locate_point(fence, (2, 2))   # returns 'inside'
locate_point(fence, (3, 5))   # returns 'outside'
locate_point(fence, (6, 3))   # returns 'boundary'
locate_point(fence, (4, 4))   # returns 'boundary'

The fence has a notch cut into its top: (3, 5) is above the bottom of the notch at (3, 3), so it is outside, while (4, 4) lies on the sloping side from (6, 6) down to (3, 3).

Constraints

• 3 to 100,000 corners; no corner is repeated.
• Coordinates are integers between -109 and 109.

Note

With numbers this large, dividing to find where a side crosses a line can round the wrong way for a point a hair away from the fence. Every answer here is exact, so use whole-number arithmetic such as cross products instead.