-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathtriangles.py3
156 lines (139 loc) · 5.74 KB
/
triangles.py3
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
154
155
156
# Copyright (c) 2022 kamyu. All rights reserved.
#
# Google Code Jam 2022 Virtual World Finals - Problem E. Triangles
# https://codingcompetitions.withgoogle.com/codejam/round/000000000087762e/0000000000b9c555
#
# Time: O(N^2), pass in PyPy3 but Python3
# Space: O(N)
#
def vector(a, b):
return [a[0]-b[0], a[1]-b[1]]
def inner_product(a, b):
return a[0] * b[0] + a[1] * b[1]
def outer_product(a, b):
return a[0] * b[1] - a[1] * b[0]
def ccw(a, b, c):
return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
# Return true if t is strictly inside a, b line segment
def is_strictly_inside_segment(t, a, b):
return ccw(t, a, b) == 0 and inner_product(vector(a, t), vector(t, b)) > 0
# Return true if t is strictly inside a, b, c triangle
def is_stricly_inside_triangle(t, a, b, c):
d1, d2, d3 = ccw(t, a, b), ccw(t, b, c), ccw(t, c, a)
return (d1 > 0 and d2 > 0 and d3 > 0) or (d1 < 0 and d2 < 0 and d3 < 0)
# Return true if t is inside a, b, c triangle
def is_inside_triangle(t, a, b, c):
d1, d2, d3 = ccw(t, a, b), ccw(t, b, c), ccw(t, c, a)
return (d1 >= 0 and d2 >= 0 and d3 >= 0) or (d1 <= 0 and d2 <= 0 and d3 <= 0)
def cross(A, B, C, D):
return ccw(A,C,D) * ccw(B,C,D) < 0 and ccw(A,B,C) * ccw(A,B,D) < 0
def insort(P, sorted_remain, x):
sorted_remain.insert(next((i for i, y in enumerate(sorted_remain) if P[y] > P[x]), len(sorted_remain)), x)
def remove_unused(P, sorted_remain, C, a, v):
cnt = sum(outer_product(v, vector(P[a], p)) == 0 for p in P)
for _ in range(max(cnt-2*(len(P)-cnt), 0)):
sorted_remain.remove(C.pop())
def find_nearest_point(P, sorted_remain, x, y):
d1, z1, v1 = float("inf"), -1, []
d2, z2, v2 = float("inf"), -1, []
u = vector(P[y], P[x])
for c in sorted_remain:
v = vector(P[y], P[c])
side = outer_product(u, v)
if side == 0:
continue
d = inner_product(v, v)
if side > 0:
if z1 != -1 and outer_product(v1, v) == 0:
if d < d1:
d1, z1, v1 = d, c, v
elif z1 == -1 or outer_product(v1, v) < 0:
d1, z1, v1 = d, c, v
else:
if z2 != -1 and outer_product(v2, v) == 0:
if d < d2:
d2, z2, v2 = d, c, v
elif z2 == -1 or outer_product(v2, v) > 0:
d2, z2, v2 = d, c, v
return z1 if z1 != -1 else z2
def make_triangle_from_max_points(P, sorted_remain, result):
x, y = sorted_remain[-1], sorted_remain[-2]
z = find_nearest_point(P, sorted_remain, x, y)
if z == -1:
return False
result.append((x, y, z))
for i in result[-1]:
sorted_remain.remove(i)
return True
def make_triangles_from_max_colinear(P, sorted_remain, C, result):
other, colinear = [], []
for x in sorted_remain:
if x not in C:
other.append(x)
else:
colinear.append(x)
for _ in range(len(colinear)//2):
x, y = colinear.pop(), colinear.pop()
z = find_nearest_point(P, other, x, y)
other.remove(z)
result.append((x, y, z))
for i in result[-1]:
sorted_remain.remove(i)
def check(x, y, z, a, b, c):
if ((sum(is_stricly_inside_triangle(t, a, b, c) for t in (x, y, z)) == 1 and
sum(not is_inside_triangle(t, a, b, c) for t in (x, y, z)) == 2) or
(sum(is_stricly_inside_triangle(t, x, y, z) for t in (a, b, c)) == 1 and
sum(not is_inside_triangle(t, x, y, z) for t in (a, b, c)) == 2)):
return False
for A, B in ((x, y), (y, z), (z, x)):
for C, D in ((a, b), (b, c), (c, a)):
if cross(A, B, C, D) or (ccw(A, C, D) == ccw(B, C, D) == 0 and
(is_strictly_inside_segment(A, C, D) or is_strictly_inside_segment(B, C, D) or
is_strictly_inside_segment(C, A, B) or is_strictly_inside_segment(D, A, B))):
return False
return True
def make_triangles_by_brute_force(P, sorted_remain, result):
i = 0
for j in range(i+1, len(sorted_remain)):
for k in range(j+1, len(sorted_remain)):
x, y, z = sorted_remain[i], sorted_remain[j], sorted_remain[k]
if ccw(P[x], P[y], P[z]) == 0:
continue
a, b, c = [o for o in sorted_remain if o not in (x, y, z)]
if ccw(P[a], P[b], P[c]) == 0 or not check(P[x], P[y], P[z], P[a], P[b], P[c]):
continue
for A, B, C in ((x, y, z), (a, b, c)):
result.append((A, B, C))
for i in result[-1]:
sorted_remain.remove(i)
return
assert(False)
def triangles():
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
result = []
removed = False
sorted_remain = sorted(range(N), key=lambda x: P[x])
while len(sorted_remain) >= 3:
if make_triangle_from_max_points(P, sorted_remain, result):
continue
a, b = sorted_remain[:2]
v = vector(P[a], P[b])
C = set(sorted_remain)
if not removed:
removed = True
remove_unused(P, sorted_remain, C, a, v)
if not sorted_remain:
break
while len(C)//2 > (len(sorted_remain)-len(C)):
for i in result.pop():
insort(P, sorted_remain, i)
if outer_product(v, vector(P[a], P[i])) == 0:
C.add(i)
if len(C) == 3 and len(sorted_remain) == 6:
make_triangles_by_brute_force(P, sorted_remain, result)
break
make_triangles_from_max_colinear(P, sorted_remain, C, result)
return "%s\n%s" % (len(result), "\n".join(map(lambda x: " ".join(map(lambda y: str(y+1), x)), result))) if result else 0
for case in range(int(input())):
print('Case #%d: %s' % (case+1, triangles()))