LeetCode 解题 Day 03

587. Erect the Fence

https://leetcode.com/problems/erect-the-fence/

题目解释

你有n棵树的座标，请你用栅栏把树全部围起来，因为栅栏太贵了所以请围出最短的距离

这题简单来说就是凸包(convex hull)的问题

解法1:

这个解法是Jarvis' March又叫做礼物包装演算法(Gift Wrapping Algorithm)，概念是先找出最外侧的任意点，之後用外积找出其他也是最外侧的点，总之先上程序码吧!

程序码:

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:

        if len(trees) <= 3:
            return trees
        
        start = self.find_start_pos(trees)
        hull = []
        p = start
        q = 0
        
        while True:
            
            q = (p + 1) % len(trees)
            
            for i in range(len(trees)):
                if self.orientation(trees[p], trees[i], trees[q]) < 0: 
                # i在逆时钟方向，可以当作最外圈的候选
                    q = i
            
            for i in range(len(trees)):
                if i != p and i != q and self.orientation(trees[p], trees[i], trees[q]) == 0: 
                # 同一条线上
                    x = trees[p][0] <= trees[i][0] and trees[i][0] <= trees[q][0] \
                            or trees[p][0] >= trees[i][0] and trees[i][0] >= trees[q][0]
                    y = trees[p][1] <= trees[i][1] and trees[i][1] <= trees[q][1] \
                            or trees[p][1] >= trees[i][1] and trees[i][1] >= trees[q][1]
                    
                    if x and y:
                        hull.append(trees[i]);
                    
            hull.append(trees[q])
            p = q
            
            if p == start:
                break
        
        return hull
    
    def find_start_pos(self, trees):
        # 找起始的点
        start = 0
        for i, tree in enumerate(trees):
            if math.sqrt(tree[0]**2 + tree[1]**2) < math.sqrt(trees[start][0]**2 + trees[start][1]**2):
                start = i
                
        return start
    
    def orientation(self, p, q, r):
        #外积
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

步骤:

先找出任意最外侧的点，因为这题已经限制 x,y 不会有负数了，所以我找最接近 (0,0) 的当起始点 p0
找起始点以外的第二个点 p1 ，接着用回圈让所有点轮流当第三个点p2，用 (p0,p1) 的向量和 (p1,p2) 的向量做外积，判断p2是不是逆时钟方向的点；简单来说就是看 p2 是不是在 (p0,p1) 向量右边
找到p2後，检查是不是有点在 p0、p2 之间，是的话也要存起来