Point in Polygon

n, m = map(int, input().split())
poly = []

for _ in range(n):
    x, y = map(int, input().split())
    poly.append((x, y))

for _ in range(m):
    px, py = map(int, input().split())
    p = (px, py)
    on_boundary = False
    for i in range(n):
        a, b = poly[i], poly[(i + 1) % n]
        if ((b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) == 0 and
    (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))):
            on_boundary = True
            break

    if on_boundary:
        print("BOUNDARY")
    else:
        cnt = 0
        for i in range(n):
            a, b = poly[i], poly[(i + 1) % n]
            if a[1] > b[1]:
                a, b = b, a
            if a[1] <= py < b[1]:
                x = a[0] + (py - a[1]) * (b[0] - a[0]) / (b[1] - a[1])
                if px < x:
                    cnt += 1
        print("INSIDE" if cnt % 2 == 1 else "OUTSIDE")

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