| Task: | Point in Polygon |
| Sender: | aalto26jm_004 |
| Submission time: | 2026-11-09 17:41:57 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | WRONG ANSWER | 0.07 s | details |
| #2 | WRONG ANSWER | 0.32 s | details |
| #3 | ACCEPTED | 0.04 s | details |
| #4 | ACCEPTED | 0.04 s | details |
| #5 | WRONG ANSWER | 0.04 s | details |
| #6 | WRONG ANSWER | 0.04 s | details |
| #7 | WRONG ANSWER | 0.04 s | details |
| #8 | WRONG ANSWER | 0.04 s | details |
| #9 | ACCEPTED | 0.04 s | details |
| #10 | ACCEPTED | 0.04 s | details |
| #11 | ACCEPTED | 0.04 s | details |
| #12 | ACCEPTED | 0.04 s | details |
| #13 | WRONG ANSWER | 0.04 s | details |
| #14 | ACCEPTED | 0.05 s | details |
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 not orient(*edge, p):
out.append('BOUNDARY')
boundary = True
break
if boundary :
continue
seg = (p, (10**9, p[1]))
ans = 0
for j in range(-1,n-1): #check if inside
edge = (poly_pts[j], poly_pts[j+1])
inter = intersect(*edge, *seg)
# print(p, inter)
ans = ans+inter %2
if ans == 1 :
out.append('INSIDE')
else :
out.append('OUTSIDE')
print('\n'.join(out))Test details
Test 1
Verdict: WRONG ANSWER
| input |
|---|
| 100 1000 -7 -19 91 77 100 100 64 60 ... |
| correct output |
|---|
| INSIDE OUTSIDE INSIDE INSIDE INSIDE ... |
| user output |
|---|
| OUTSIDE OUTSIDE OUTSIDE OUTSIDE OUTSIDE ... |
Feedback: Output is shorter than expected
Test 2
Verdict: WRONG ANSWER
| input |
|---|
| 1000 1000 365625896 -113418831 278762563 38777445 250367343 -96991975 175866909 -129766978 ... |
| correct output |
|---|
| OUTSIDE OUTSIDE INSIDE OUTSIDE OUTSIDE ... |
| user output |
|---|
| OUTSIDE OUTSIDE OUTSIDE OUTSIDE OUTSIDE ... |
Feedback: Incorrect character on line 3 col 1: expected "INSIDE", got "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: WRONG ANSWER
| 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: WRONG ANSWER
| input |
|---|
| 8 1 0 0 0 2 1 1 2 2 ... |
| correct output |
|---|
| INSIDE |
| user output |
|---|
| BOUNDARY |
Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "BOUNDARY"
Test 7
Verdict: WRONG ANSWER
| input |
|---|
| 4 4 0 0 3 0 3 4 0 4 ... |
| correct output |
|---|
| INSIDE BOUNDARY OUTSIDE BOUNDARY |
| user output |
|---|
| INSIDE BOUNDARY BOUNDARY |
Feedback: Output is shorter than expected
Test 8
Verdict: WRONG ANSWER
| input |
|---|
| 6 1 0 0 0 2 3 1 2 2 ... |
| correct output |
|---|
| INSIDE |
| user output |
|---|
| OUTSIDE |
Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"
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: WRONG ANSWER
| 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 ... |
