Point in Polygon

def on_segment(p, q, r):
    """Check if point q lies on segment pr."""
    return min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and min(p[1], r[1]) <= q[1] <= max(p[1], r[1])

def orientation(p, q, r):
    """Find the orientation of the triplet (p, q, r).
    0 -> p, q, r are collinear
    1 -> Clockwise
    2 -> Counterclockwise
    """
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # Collinear
    elif val > 0:
        return 1  # Clockwise
    else:
        return 2  # Counterclockwise

def is_point_on_boundary(polygon, point):
    """Check if a point is on the boundary of the polygon."""
    n = len(polygon)
    for i in range(n):
        p1, p2 = polygon[i], polygon[(i + 1) % n]
        if orientation(p1, p2, point) == 0 and on_segment(p1, point, p2):
            return True
    return False

def is_point_inside(polygon, point):
    """Check if a point is inside the polygon using the ray-casting algorithm."""
    n = len(polygon)
    x, y = point
    count = 0
    for i in range(n):
        p1, p2 = polygon[i], polygon[(i + 1) % n]
        if y >= min(p1[1], p2[1]) and y < max(p1[1], p2[1]):
            if x <= max(p1[0], p2[0]):
                if p1[1] != p2[1]:
                    xinters = (y - p1[1]) * (p2[0] - p1[0]) / (p2[1] - p1[1]) + p1[0]
                if p1[0] == p2[0] or x <= xinters:
                    count += 1
    return count % 2 == 1

def polygon_point_check(n, m, polygon, points):
    for point in points:
        if is_point_on_boundary(polygon, point):
            print("BOUNDARY")
        elif is_point_inside(polygon, point):
            print("INSIDE")
        else:
            print("OUTSIDE")

# Input parsing
n, m = map(int, input().split())
polygon = [tuple(map(int, input().split())) for _ in range(n)]
points = [tuple(map(int, input().split())) for _ in range(m)]

# Output results
polygon_point_check(n, m, polygon, points)

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