Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一堆树的坐标,用最小的多边形围住这些树,求问最后哪些树在多边形的顶点上,凸包模板题
借鉴了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))

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理