-
Notifications
You must be signed in to change notification settings - Fork 7
/
polygongame.py
153 lines (146 loc) · 6.4 KB
/
polygongame.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
'''
Here's a random TC for you!
Input:
25 50
23 44
24 47
25 49
27 52
28 53
31 55
33 56
36 57
40 58
44 57
47 56
49 55
52 53
53 52
55 49
56 47
57 44
58 40
57 36
56 33
55 31
53 28
52 27
49 25
47 24
56.64534672702648 34.93604018107942 44.88378003862929 56.705406653790234
24.203811717201233 47.407623434402474 57.075507329856606 36.30202931942643
53.773690889325835 29.16053633398876 50.321015902979696 54.11932273134687
56.57547894438971 45.27356316683087 57.059255400725505 36.23702160290202
37.73409686700131 31.721585944165575 35.10344339346007 56.70114779782003
55.483816260019225 31.967632520038457 37.027200113286696 32.310666572261084
54.097608085522864 29.646412128284297 50.08993680480811 54.27337546346126
55.81896834711587 32.637936694231755 23.38419099032341 45.15257297097023
37.804388647937444 57.451097161984364 48.38364243700259 24.6918212185013
47.08560583740816 24.04280291870408 45.32256032175777 56.559146559414074
27.8393270903783 52.8393270903783 48.94364135809159 55.02817932095421
53.37131139964893 28.5569670994734 52.55109051220336 27.551090512203366
46.85656327758017 56.04781224080661 57.300042534218264 42.79982986312695
31.143804545042272 55.071902272521136 27.47782519526492 52.47782519526492
30.81360070665515 54.87573380443676 45.86480341810997 56.37839886063001
50.739639239694 53.84024050687067 57.858695421189424 39.43478168475772
56.90172327191148 44.294830184265564 24.649189312181043 48.29837862436209
53.05535952825723 28.08303929238584 27.087266931087232 52.087266931087235
55.3433098053988 48.31338038920239 27.926533595800038 52.92653359580004
23.653121150643152 45.95936345192946 27.741050197356348 52.741050197356344
54.74395365297513 30.615930479462698 43.396726077278494 57.15081848068038
52.29599932121448 52.70400067878551 48.29860650889725 24.649303254448625
31.631462541973598 55.3157312709868 56.98724005953928 44.038279821382154
24.159087285089687 47.31817457017937 48.09984013670456 55.45007993164772
48.526371687566574 55.23681415621671 57.25472737881469 37.01890951525877
53.174590623299906 28.261885934949863 23.82544400100519 46.47633200301557
23.911440141897323 46.73432042569197 52.818435393988 27.818435393987997
26.091912671019927 50.6378690065299 49.56466333526396 25.376442223509304
49.52622375082598 25.350815833883985 56.839855439904085 44.48043368028773
52.07562874819762 27.07562874819762 47.47423594286056 55.76288202856972
57.09428042203955 36.3771216881582 51.688152280835624 53.20789847944292
28.656885993075612 53.43792399538374 32.64680840967906 35.96099299193412
57.51772714605617 41.92909141577533 52.16311242157493 52.83688757842507
36.23306880571464 32.972442661904466 39.87519160055673 57.96879790013919
27.428678677282456 52.428678677282456 55.7682467535467 47.46350649290661
52.1130105080879 27.113010508087903 53.4318006884392 51.3522989673412
51.349566793524744 26.566377862349835 57.409719603123435 37.63887841249375
23.145924887165357 44.43777466149607 35.36772547420126 56.78924182473375
57.34068398281991 37.36273593127963 46.34556269676323 24.545364419363974
42.166345134745555 57.458413716313615 57.799086432269874 39.19634572907952
48.15566698649541 24.577833493247706 35.97445940951082 33.187950492074314
43.168451033730584 27.19295747189118 55.074825452374114 31.14965090474822
56.27156598228308 46.185302053150764 54.76378690153331 49.35431964770004
57.385986872491216 42.45605251003512 26.090313302740824 50.63546995411123
32.247632910094055 55.62381645504703 55.534595223156344 32.06919044631269
55.684304792773176 32.368609585546366 45.6434015064594 56.45219949784687
24.415527097262128 42.82039408561489 47.16070545887587 24.080352729437934
42.99926469848483 57.25018382537879 33.989692967726505 56.32989765590884
25.49889613612264 49.74834420418396 40.32060407775751 57.919848980560616
33.774269278740505 35.021442267716246 48.07765949758054 24.53882974879027
Output:
28.577475294554404
'''
EPS = 1e-7
def intersect(s1, s2):
(p1, p2), (p3, p4) = s1, s2
(x1, y1), (x2, y2), (x3, y3), (x4, y4) = p1, p2, p3, p4
a, b, c = y2-y1, x1-x2, (y2-y1)*x1 - (x2-x1)*y1
d, e, f = y4-y3, x3-x4, (y4-y3)*x3 - (x4-x3)*y3
det = b*d-a*e
if abs(det) > EPS:
x, y = (b*f-c*e)/det, (c*d-a*f)/det; return (x, y) if (
min(x1, x2)-EPS <= x <= max(x1, x2)+EPS and
min(y1, y2)-EPS <= y <= max(y1, y2)+EPS and
min(x3, x4)-EPS <= x <= max(x3, x4)+EPS and
min(y3, y4)-EPS <= y <= max(y3, y4)+EPS and
abs(a*x+b*y-c) < EPS and
abs(d*x+e*y-f) < EPS
) else None
def area(p):
a, n = 0, len(p)
for i in range(n): a += p[i][0]*p[(i+1)%n][1]-p[i][1]*p[(i+1)%n][0]
return abs(a)/2
def dist(p1, p2):
return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**.5
N, M = map(int, input().split()); P = [tuple(map(float, input().split())) for _ in range(N)]; Q = [P]
for _ in range(M):
x1, y1, x2, y2 = map(float, input().split()); S = ((x1, y1), (x2, y2)); R = []
for p in Q:
I = []; X = []
for i in range(len(p)):
s = (p[i], p[(i+1)%len(p)]); x = intersect(s, S)
if x:
if dist(x, s[0]) > EPS and dist(x, s[1]) > EPS: I.append((x, i))
if dist(x, s[0]) < EPS: X.append(i)
if len(I)+len(X) != 2: R.append(p)
else:
p1 = []; p2 = []
if len(I) == 2: # both intersect on non-endpoints
p1.append(I[0][0]); p2.append(I[1][0]); x = (I[0][1]+1)%len(p)
while 1:
p1.append(p[x])
if x == I[1][1]: p1.append(I[1][0]); break
x = (x+1)%len(p)
x = (x+1)%len(p)
while 1:
p2.append(p[x])
if x == I[0][1]: p2.append(I[0][0]); break
x = (x+1)%len(p)
elif len(X) == 2: # both intersect on endpoints
x = X[0]
while x != X[1]: p1.append(p[x]); x = (x+1)%len(p)
p1.append(p[x])
while x != X[0]: p2.append(p[x]); x = (x+1)%len(p)
p2.append(p[x])
else: # one endpoint, one non-endpoint
x = X[0]
while 1:
p1.append(p[x])
if x == I[0][1]: p1.append(I[0][0]); break
x = (x+1)%len(p)
p2.append(I[0][0]); x = (x+1)%len(p)
while x != X[0]: p2.append(p[x]); x = (x+1)%len(p)
p2.append(p[x])
R.append(p1); R.append(p2)
Q = R
print(max(map(area, Q)))