Posted on 2022-11-19 18:52
Uriel 閱讀(52)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
計(jì)算幾何 、
閑來無事重切Leet Code
給出一堆樹的坐標(biāo)，用最小的多邊形圍住這些樹，求問最后哪些樹在多邊形的頂點(diǎn)上，凸包模板題
借鑒了https://leetcode.com/problems/erect-the-fence/discuss/1442266/A-Detailed-Explanation-with-Diagrams-(Graham-Scan) 的做法，先對(duì)樹坐標(biāo)先x后y排序，在分上下半塊凸包分別構(gòu)建
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))