CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:ashum-ta
Submission time:2024-11-11 16:55:48 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#10.06 sdetails
#20.06 sdetails
#30.06 sdetails
#40.06 sdetails
#50.06 sdetails
#60.06 sdetails
#70.06 sdetails
#80.06 sdetails
#90.06 sdetails
#100.06 sdetails
#110.07 sdetails
#120.06 sdetails
#130.06 sdetails

Code

import sys
import math
input = sys.stdin.readline
 
def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
 
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
 
 
class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b
 
 
def cross_product(p, q):
    #x1y2 − x2y1
    return p.x * q.y - p.y * q.x
 
 
def from_the_line(p, s):
    #(p−s1)×(p−s2)
    return cross_product(p - s.a, p - s.b)
 
 
def on_the_line(p, s):
    return (cross_product(p - s.a, p - s.b) == 0 and (min(s.a.y, s.b.y) <= p.y <= max(s.a.y, s.b.y)) and
            (min(s.a.x, s.b.x) <= p.x <= max(s.a.x, s.b.x)))
 
 
def same_line(p, q):
    return on_the_line(p.a, q) or on_the_line(p.b, q) or on_the_line(q.a, p) or on_the_line(q.b, p)
 
 
def end_intersection(p, q):
    return p.a == q.a or p.a == q.b or p.b == q.b or p.b == q.a
 
 
def middle_intersection(p, q):
    return ((from_the_line(p.a, q) * from_the_line(p.b, q)) < 0) and
            (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))
 
 
n, m = map(int, input().split())
polygon_points = []
polygon_lines = []
maxx = -math.inf
maxy = -math.inf
 
for i in range(n):
    x, y = map(int, input().split())
    p = Point(x, y)
    maxx = max(maxx, p.x)
    maxy = max(maxy, p.y)
    polygon_points.append(p)
    # if same_line(l1, l2) or end_intersection(l1, l2) or middle_intersection(l1, l2):
    #     print('YES')
    # else:
    #     print('NO')
# print(polygon_points)
 
 
for i in range(1, n):
    l = Line(polygon_points[i], polygon_points[i - 1])
    polygon_lines.append(l)
polygon_lines.append(Line(polygon_points[n - 1], polygon_points[0]))
 
 
for i in range(m):
    x, y = map(int, input().split())
    p = Point(x, y)
 
    on_the_border = False
    line = Line(p, Point(maxx * 10, maxy * 10 + 1))
    inter = 0
    for l in polygon_lines:
        if max(l.a.x, l.b.x) <= p.x or max(l.a.y, l.b.y) <= p.y:
            pass
        if on_the_line(p, l):
            on_the_border = True
            break
        if middle_intersection(line, l):
            inter += 1
    if on_the_border:
        print('BOUNDARY')
    elif inter % 2 == 0:
        print('OUTSIDE')
    else:
        print('INSIDE')
 
 

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
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 2

Verdict:

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

correct output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 3

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 4

Verdict:

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

correct output
OUTSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 5

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 6

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 7

Verdict:

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

correct output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 8

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 9

Verdict:

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

correct output
OUTSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 10

Verdict:

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

correct output
OUTSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 11

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 12

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...

Test 13

Verdict:

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

correct output
INSIDE

user output
(empty)

Error:
File "input/code.py", line 53
    (from_the_line(q.a, p) * from_the_line(q.b, p)) < 0))...