【面】周长最小的外接多边形

示例1:
输入:[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出:[[1,1],[2,0],[4,2],[3,3],[2,4]]
解释:

示例2:
输入:[[1,2],[2,2],[4,2]]
输出:[[1,2],[2,2],[4,2]]
解释:

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
class Solution:
def outerTrees(self, points):
def cross(a,b,c):
res = (b[0]-a[0])*(c[1]-b[1])-(c[0]-b[0]) * (b[1]-a[1]) # ab × bc
# print(res)
return res

n = len(points)
if n < 3:
return points
points.sort(key = lambda x:(x[0],x[1]))
# print(points)

low = []
for p in points:
# print("low:", low)
while len(low) > 1 and cross(low[-2],low[-1],p) < 0: # 如果low[-1]p 在 low[-2]low[-1]的顺时针
# print("low:", low)
low.pop()
low.append((p[0],p[1]))
# print("up start")
up = []
for p in reversed(points):
while len(up) > 1 and cross(up[-2],up[-1],p) < 0:
# print("up:", up)
up.pop()
up.append((p[0],p[1]))
# print(low, up)
return list(set(low[:-1] + up[:-1]))

if __name__=='__main__':
s = Solution()
print(s.outerTrees([[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]))
0%