Point in Polygon

def on_segment(px, py, x1, y1, x2, y2):
    if min(x1, x2) <= px <= max(x1, x2) and min(y1, y2) <= py <= max(y1, y2):
        dx1, dy1 = x2 - x1, y2 - y1
        dx2, dy2 = px - x1, py - y1
        return dx1 * dy2 == dx2 * dy1
    return False

n, m = map(int, input().split())
poly = [tuple(map(int, input().split())) for _ in range(n)]
points = [tuple(map(int, input().split())) for _ in range(m)]
# Ray casting algorithm
for px, py in points:
    boundary = False
    cnt = 0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        if on_segment(px, py, x1, y1, x2, y2):
            boundary = True
            break
        if y1 <= py < y2 or y2 <= py < y1:
            x_int = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
            if x_int > px:
                cnt += 1
    if boundary:
        print("BOUNDARY")
    elif cnt % 2 == 1:
        print("INSIDE")
    else:
        print("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