Submission details
Task:Point in Polygon
Sender:aalto26jm_004
Submission time:2026-11-09 18:17:20 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#10.45 sdetails
#2ACCEPTED0.39 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.04 sdetails
#50.04 sdetails
#6ACCEPTED0.04 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.04 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.04 sdetails
#130.04 sdetails
#14ACCEPTED0.06 sdetails

Code

import sys

def cross(a, b):
    # print(a, b)
    return a[0]*b[1] - a[1]*b[0]

def on_seg(a,b,p):
    return (min(a[0], b[0]) <= p[0] <= max(a[0],b[0]) and 
            min(a[1], b[1]) <= p[1] <= max(a[1],b[1]))

def orient(a, b, c):
    o = cross((b[0]-a[0], b[1]-a[1]), (c[0]-a[0], c[1]-a[1]))
    return (o>0) - (o<0)

def intersect(a,b,c,d):
        o1 = orient(a, b, c)
        o2 = orient(a, b, d)
        o3 = orient(c, d, a)
        o4 = orient(c, d, b)
        if (o1!= o2) and (o3!= o4):
            return 1
        if (not o1) and on_seg(a, b, c):
            return 1
        if (not o2) and on_seg(a, b, d):
            return 1
        if (not o3) and on_seg(c, d, a): 
            return 1
        if (not o4) and on_seg(c, d, b):
            return 1
        return 0


n, m = map(int, input().split())
l = sys.stdin.read().strip().split('\n')
poly_pts = [tuple(map(int, line.split())) for line in l[:n]]
pts = [tuple(map(int, line.split())) for line in l[n:]]
# print(poly_pts, pts)
out = []
boundary = False
for p in pts:
    for j in range(-1,n-1): #check if boundary
        edge = (poly_pts[j], poly_pts[j+1])
        if (on_seg(*edge, p) and not orient(*edge, p)):
            out.append('BOUNDARY')
            boundary = True
            break
    if boundary :
        boundary = 0
        continue

    seg = (p, (10**9, p[1]))
    is_point_inside = 0
    for j in range(-1,n-1): #check if inside
        edge = (poly_pts[j], poly_pts[j+1])
        if edge[1][1]==p[1] and edge[0][1]==p[1] and p[0]<edge[0][0] and p[0]<edge[1][0]:
            is_point_inside = 1-is_point_inside
        else :
            if intersect(*edge, *seg):
                is_point_inside = 1-is_point_inside
            # print(p, inter)
    if is_point_inside == 1 :
        out.append('INSIDE')
    else :
        out.append('OUTSIDE')


print('\n'.join(out))

Test details

Test 1

Verdict:

input
100 1000
-7 -19
91 77
100 100
64 60
...

correct output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

user output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

Feedback: Incorrect character on line 12 col 1: expected "OUTSIDE", got "INSIDE"

Test 2

Verdict: ACCEPTED

input
1000 1000
365625896 -113418831
278762563 38777445
250367343 -96991975
175866909 -129766978
...

correct output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

user output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

Test 3

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
INSIDE

user output
INSIDE

Test 4

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
OUTSIDE

user output
OUTSIDE

Test 5

Verdict:

input
4 1
1 100
2 50
1 20
0 50
...

correct output
INSIDE

user output
OUTSIDE

Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"

Test 6

Verdict: ACCEPTED

input
8 1
0 0
0 2
1 1
2 2
...

correct output
INSIDE

user output
INSIDE

Test 7

Verdict: ACCEPTED

input
4 4
0 0
3 0
3 4
0 4
...

correct output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

user output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

Test 8

Verdict: ACCEPTED

input
6 1
0 0
0 2
3 1
2 2
...

correct output
INSIDE

user output
INSIDE

Test 9

Verdict: ACCEPTED

input
3 1
0 0
1 1000000000
-3 0
1 1

correct output
OUTSIDE

user output
OUTSIDE

Test 10

Verdict: ACCEPTED

input
3 1
-100000 0
-1000000000 -999999999
1000000000 1000000000
0 0

correct output
OUTSIDE

user output
OUTSIDE

Test 11

Verdict: ACCEPTED

input
3 1
-100000 0
-999999999 -1000000000
1000 1000
0 0

correct output
INSIDE

user output
INSIDE

Test 12

Verdict: ACCEPTED

input
4 1
-4 1
-6 1
-6 -1
-4 -1
...

correct output
INSIDE

user output
INSIDE

Test 13

Verdict:

input
3 1
0 10
0 -10
10 0
1 0

correct output
INSIDE

user output
OUTSIDE

Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"

Test 14

Verdict: ACCEPTED

input
3 1000
-536621709 -536621709
955833081 955833081
-1 1
-439278425 -439278425
...

correct output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...

user output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...