|
1
|
|
|
from math import acos, degrees, hypot |
|
2
|
|
|
|
|
3
|
|
|
|
|
4
|
|
|
def CalcAngle(P1, P2): |
|
5
|
|
|
if P2[0] < P1[0]: |
|
6
|
|
|
return 360 - degrees( |
|
7
|
|
|
acos((P2[1] - P1[1]) * 1.0 / hypot(P2[0] - P1[0], P2[1] - P1[1])) |
|
8
|
|
|
) |
|
9
|
|
|
return round( |
|
10
|
|
|
degrees(acos((P2[1] - P1[1]) * 1.0 / hypot(P2[0] - P1[0], P2[1] - P1[1]))), 0 |
|
11
|
|
|
) |
|
12
|
|
|
|
|
13
|
|
|
|
|
14
|
|
|
def CalcDistance(P1, P2): |
|
15
|
|
|
return hypot(P1[0] - P2[0], P1[1] - P2[1]) |
|
16
|
|
|
|
|
17
|
|
|
|
|
18
|
|
|
def checkio(data): |
|
19
|
|
|
"""list[list[int, int],] -> list[int,]. |
|
20
|
|
|
|
|
21
|
|
|
Find the convex hull. |
|
22
|
|
|
""" |
|
23
|
|
|
SortedData = sorted(data, key=lambda x: (x[0], x[1])) |
|
24
|
|
|
SortedData += [SortedData[0]] |
|
25
|
|
|
PointList = [] |
|
26
|
|
|
CurrentAngle = 0 |
|
27
|
|
|
CurrentPoint = SortedData[0] |
|
28
|
|
|
while 1: |
|
29
|
|
|
PointList.append(CurrentPoint) |
|
30
|
|
|
SortedData.remove(CurrentPoint) |
|
31
|
|
|
AngleList = [ |
|
32
|
|
|
CalcAngle(CurrentPoint, i) if i != CurrentPoint else 999 for i in SortedData |
|
33
|
|
|
] |
|
34
|
|
|
MinAngle = min([i for i in AngleList if i >= CurrentAngle]) |
|
35
|
|
|
NextPoint = [j for k, j in enumerate(SortedData) if AngleList[k] == MinAngle] |
|
36
|
|
|
|
|
37
|
|
|
# more than one point with same angle |
|
38
|
|
|
if len(NextPoint) != 1: |
|
39
|
|
|
DistanceList = [CalcDistance(i, CurrentPoint) for i in NextPoint] |
|
40
|
|
|
NextPoint = [ |
|
41
|
|
|
j |
|
42
|
|
|
for i, j in enumerate(NextPoint) |
|
43
|
|
|
if DistanceList[i] == min(DistanceList) |
|
44
|
|
|
] |
|
45
|
|
|
NextPoint = NextPoint[0] |
|
46
|
|
|
if PointList[0] == NextPoint: |
|
47
|
|
|
break |
|
48
|
|
|
else: |
|
49
|
|
|
CurrentAngle = min([i for i in AngleList if i >= CurrentAngle]) |
|
50
|
|
|
CurrentPoint = NextPoint |
|
51
|
|
|
return list(map(lambda x: data.index(x), PointList)) |
|
52
|
|
|
|
|
53
|
|
|
|
|
54
|
|
|
if __name__ == '__main__': |
|
55
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
56
|
|
|
# auto-testing |
|
57
|
|
|
assert checkio([[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]) == [ |
|
58
|
|
|
4, |
|
59
|
|
|
5, |
|
60
|
|
|
6, |
|
61
|
|
|
0, |
|
62
|
|
|
1, |
|
63
|
|
|
2, |
|
64
|
|
|
3, |
|
65
|
|
|
], "First example" |
|
66
|
|
|
assert checkio([[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]) == [ |
|
67
|
|
|
1, |
|
68
|
|
|
0, |
|
69
|
|
|
6, |
|
70
|
|
|
3, |
|
71
|
|
|
5, |
|
72
|
|
|
2, |
|
73
|
|
|
], "Second example" |
|
74
|
|
|
|
KenMercusLai /
checkio
