Point in Polygon

n, m = [int(x) for x in input().split()]
polygon = []
for _ in range(n):
    x, y = [int(x) for x in input().split()]
    polygon.append([x, y])

def on_segment(x1, y1, x2, y2, x3, y3):
    return (x3 - x1) * (y2 - y1) == (y3 - y1) * (x2 - x1) and (min(x1, x3) <= x2 <= max(x1, x3)) and (min(y1, y3) <= y2 <= max(y1, y3))

for _ in range(m):
    x, y = [int(x) for x in input().split()]
    intersections = 0
    boundary = False
    for i in range(n):
        j = (i+1)%n
        x1, y1 = polygon[i][0], polygon[i][1]
        x2, y2 = polygon[j][0], polygon[j][1]
        if on_segment(x1,y1,x,y,x2,y2):
            boundary = True
            break
        if ((y1 > y) != (y2 > y)):
            x_int = x1 + (y-y1)*(x2-x1)/(y2-y1)
            if x_int > x:
                intersections += 1

    if boundary:
        print("BOUNDARY")
    elif intersections%2==0:
        print("OUTSIDE")
    else:
        print("INSIDE")

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED