Posted on 2022-11-19 18:52
Uriel 阅读(32)
评论(0) 编辑 收藏 引用 所属分类:
计算几何 、
闲来无事重切Leet Code
给出一堆树的坐标，用最小的多边形围住这些树，求问最后哪些树在多边形的顶点上，凸包模板题
借鉴了https://leetcode.com/problems/erect-the-fence/discuss/1442266/A-Detailed-Explanation-with-Diagrams-(Graham-Scan) 的做法，先对树坐标先x后y排序，在分上下半块凸包分别构建
1 #587
2 #Runtime: 562 ms
3 #Memory Usage: 14.2 MB
4
5 class Solution(object):
6 def corssProduct(self, p1, p2, p3):
7 return (p3[1]-p2[1]) * (p2[0]-p1[0]) - (p2[1]-p1[1]) * (p3[0]-p2[0])
8
9 def buildConvexHull(self, points):
10 lower = []
11 upper = []
12 for pt in points:
13 while len(lower) >= 2 and self.corssProduct(lower[-2], lower[-1], pt) < 0:
14 lower.pop()
15 while len(upper) >= 2 and self.corssProduct(upper[-2], upper[-1], pt) > 0:
16 upper.pop()
17 upper.append(pt)
18 lower.append(pt)
19 return upper, lower
20
21 def outerTrees(self, trees):
22
23 """
24 :type trees: List[List[int]]
25 :rtype: List[List[int]]
26 """
27 points = sorted(trees)
28 upper, lower = self.buildConvexHull(points)
29 return set(tuple(T) for T in (upper + lower))