Task: | Point in Polygon |
Sender: | esya_rae |
Submission time: | 2024-11-11 16:51:45 +0200 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.87 s | details |
#2 | ACCEPTED | 0.71 s | details |
#3 | ACCEPTED | 0.04 s | details |
#4 | ACCEPTED | 0.04 s | details |
#5 | ACCEPTED | 0.04 s | details |
#6 | ACCEPTED | 0.04 s | details |
#7 | ACCEPTED | 0.04 s | details |
#8 | ACCEPTED | 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.05 s | details |
#13 | ACCEPTED | 0.04 s | details |
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) > 0) != (from_the_line(p.b, q) > 0) and (from_the_line(q.a, p) > 0) != (from_the_line(q.b, p) > 0)) n, m = map(int, input().split()) polygon_points = [] polygon_lines = [] maxx = 10**9 + 7 maxy = 10**9 + 7 x, y = map(int, input().split()) prev_p = Point(x, y) prev_0 = prev_p for i in range(n - 1): x, y = map(int, input().split()) cur_p = Point(x, y) polygon_lines.append(Line(prev_p, cur_p)) prev_p = cur_p polygon_lines.append(Line(prev_p, prev_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, maxy)) 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: 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 |