Point in Polygon

def on_segment(xi, yi, xj, yj, xk, yk):
    return (min(xi, xj) <= xk <= max(xi, xj)) and (min(yi, yj) <= yk <= max(yi, yj))

def area(xi, yi, xj, yj, xk, yk):
    return xk * (yi - yj) + xi * (yj - yk) + xj * (yk - yi)

def check(polygon, point):
    count = 0
    x, y = point
    n = len(polygon)
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i + 1) % n]
        if ((y1 > y) != (y2 > y)) and (x < (x2 - x1) * (y - y1) / (y2 - y1) + x1):
            count += 1
        if area(x1, y1, x2, y2, x, y) == 0 and on_segment(x1, y1, x2, y2, x, y):
            return "BOUNDARY"
    if count % 2 == 1:
        return "INSIDE"
    else:
        return "OUTSIDE"



if __name__ == "__main__":
    n, m = map(int, input().split())
    polygon = []
    for _ in range(n):
        x, y = map(int, input().split())
        polygon.append((x, y))
    points = []
    for _ in range(m):
        x, y = map(int, input().split())
        points.append((x, y))
    for point in points:
        print(check(polygon, point))

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