Point in Polygon

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def cross(a, b, c):
    u = Point(b.x - a.x, b.y - a.y)
    v = Point(c.x - a.x, c.y - a.y)
    cp = u.x * v.y - u.y * v.x
    return cp

def mid(a, b, c):
    if (c.x >= min(a.x, b.x) and c.x <= max(a.x, b.x) and
        c.y >= min(a.y, b.y) and c.y <= max(a.y, b.y)):
        cp = cross(a, b, c)
        if cp == 0:
            return True
    return False

def check(a, b, c, d):
    cp1 = cross(a, b, c)
    cp2 = cross(a, b, d)
    cp3 = cross(c, d, a)
    cp4 = cross(c, d, b)
    if cp1 * cp2 < 0 and cp3 * cp4 < 0:
        return True
    if cp3 == 0 and mid(c, d, a) and cp4 < 0:
        return True
    if cp4 == 0 and mid(c, d, b) and cp3 < 0:
        return True
    return False

inp = input().split(' ')
n = int(inp[0])
m = int(inp[1])
vertices = []
for i in range(n):
    inp = input().split(' ')
    x = int(inp[0])
    y = int(inp[1])

    vertices.append(Point(x, y))

points = []

for i in range(m):
    inp = input().split(' ')
    x = int(inp[0])
    y = int(inp[1])

    points.append(Point(x, y))



polygon = vertices + [vertices[0]]

INF = 10 ** 9 + 7

for point in points:
    cnt = 0
    flag = 0
    infinity = Point(INF, INF)
    for j in range(n):
        cp = cross(polygon[j], polygon[j + 1], point)
        if cp == 0 and mid(polygon[j], polygon[j + 1], point):
            flag = 1
            break
        cnt += 1 if check(polygon[j], polygon[j + 1], point, infinity) else 0
    if flag == 1:
        print("BOUNDARY")
    else:
        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