Submission details
Task:Point in Polygon
Sender:aalto26jm_001
Submission time:2026-11-09 17:08:13 +0200
Language:Python3 (PyPy3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.07 sdetails
#2ACCEPTED0.10 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.05 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.05 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.05 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.05 sdetails
#14ACCEPTED0.06 sdetails

Code

# FULL TEMPLATE: delete every block you don't use. Blocks don't depend on each other.
# Nodes are 1..n (slot 0 unused). Arrays are 0-indexed.
import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from itertools import accumulate, permutations, combinations, product
from functools import lru_cache, cmp_to_key
from math import gcd, isqrt, comb, inf
input = sys.stdin.readline
MOD = 10**9 + 7

def I():  return int(input())                    # "5"          -> 5
def MI(): return map(int, input().split())       # "8 4"        -> n, q = MI()
def LI(): return list(map(int, input().split())) # "3 2 4 5"    -> [3, 2, 4, 5]
def S():  return input().strip()                 # "BABAZA", ".*.#" (kept as text)
def LS(): return input().split()                 # "? 2 3"      -> ['?', '2', '3']

def point_in_polygon(poly, p):  # "INSIDE" / "OUTSIDE" / "BOUNDARY" for any simple polygon, O(n)
    px, py = p
    inside = False
    ax, ay = poly[-1]
    for bx, by in poly:
        c = (bx - ax) * (py - ay) - (by - ay) * (px - ax)          # orient(a, b, p)
        if c == 0 and min(ax, bx) <= px <= max(ax, bx) and min(ay, by) <= py <= max(ay, by):
            return "BOUNDARY"
        if (ay > py) != (by > py):        # edge crosses the line y = py (half-open: a vertex
            if (c > 0) == (by > ay):      # exactly on the ray is counted once, not twice)
                inside = not inside       # ...and the crossing is to the RIGHT of p
        ax, ay = bx, by
    return "INSIDE" if inside else "OUTSIDE"

def main():
    n, m = MI()
    poly = [tuple(MI()) for _ in range(n)]
    print("\n".join(point_in_polygon(poly, tuple(MI())) for _ in range(m)))

main()

Test details

Test 1

Verdict: ACCEPTED

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
...

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: ACCEPTED

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

correct output
INSIDE

user output
INSIDE

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: ACCEPTED

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

correct output
INSIDE

user output
INSIDE

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
...