Point in Polygon

def is_point_on_segment(px, py, ax, ay, bx, by):
    if min(ax, bx) <= px <= max(ax, bx) and min(ay, by) <= py <= max(ay, by):
        cross_product = (py - ay) * (bx - ax) - (px - ax) * (by - ay)
        if cross_product == 0:
            return True
    return False

def is_point_inside_polygon(px, py, vertices):
    n = len(vertices)
    intersections = 0
    for i in range(n):
        ax, ay = vertices[i]
        bx, by = vertices[(i + 1) % n]
 
        if is_point_on_segment(px, py, ax, ay, bx, by):
            return "BOUNDARY"
      
        if ay > by:
            ax, ay, bx, by = bx, by, ax, ay

        if py == ay or py == by:
            py += 1e-9

        if ay < py < by and (px < (bx - ax) * (py - ay) / (by - ay) + ax):
            intersections += 1

    return "INSIDE" if intersections % 2 == 1 else "OUTSIDE"

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)]

results = []
for px, py in points:
    result = is_point_inside_polygon(px, py, polygon)
    results.append(result)

print("\n".join(results))

Test 1

Verdict: WRONG ANSWER

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