CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:Farah
Submission time:2024-11-11 17:24:05 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#10.28 sdetails
#2ACCEPTED0.34 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.04 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.04 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.04 sdetails

Code

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

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