587. 安装栅栏

Difficulty

Hard

Tags

数学

URL

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

Star

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

示例 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]]
解释:
即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。

输入的整数在 0 到 100 之间。

花园至少有一棵树。

所有树的坐标都是不同的。

输入的点没有顺序。输出顺序也没有要求。

通过次数7,284提交次数12,851

法1 凸包问题（Andrew 算法）

思路

对所有点进行双关键字排序，先根据 xx 坐标排升序，后根据 yy 排升序；根据 xx 排升序的目的，是为了我们能够往一个方向画出凸包边缘（从左往后画出一半凸壳，从右往左画出另外一半），而将 yy 升序目的是可以确保一旦我们现在从 aa 到 bb 进行连线，那么 aa 到 bb 之间的所有点能够确保被围住；

使用栈来维护所有凸包上的点，或者说凸包上的边，会更为准确，凸包起点元素会在栈中出现两次（首尾），因此更为准确的描述应该是使用栈维护凸包的所有的边，栈中相邻元素代表凸包上的一条边；

分别「从前往后」和「从后往前」处理排序好的所有点，来分别画出凸包的上下两部分，根据画的是第一部分还是第二部分，维护栈内元的处理逻辑稍有不同：

画的是凸包的第一部分

若栈内元素少于 2 个（组成一条线至少需要两个点），说明此时第一条边都还没画出，直接将元素添加到栈中；

若栈内元素不少于 2 个，考虑是否要将栈顶的边删掉（由栈顶前两个元素组成的边）假设栈顶元素为 b，栈顶元素的下一位为 a，即栈顶存在一条 a 到 b 的边，当前处理到的点为 c，此时我们根据 ac 边是否在 ab 边的时针方向来决定是否要将 ab 边去掉：

画的是凸包的第二部分

逻辑同理，唯一需要注意的是，第一部分的凸包边我们不能删去，假定处理完第一部分凸包，我们栈内有 m 个元素，我们需要将上述「栈顶元素不少于 2 个」的逻辑替换为「栈顶元素大于 m 个」，同时已参与到凸包第一部分的点，不能再考虑，因此需要额外使用一个 visvis 数组来记录使用过的点。

vis 的作用仅是为了处理凸包第二部分的时候，不要使用到凸包第一部分的点而已。含义并非是处理过的点，或者当前凸包上的点

题解


class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        if len(trees) < 4:
            return trees

        trees.sort()
        stack = []

        # visited 标记的是作为凸包顶点的点
        visited = [False] * len(trees)
        
        stack.append(0)
        # 找上凸包
        for i in range(1, len(trees)):
            while len(stack) >= 2 and \
                    self.cross(trees[stack[-2]], trees[stack[-1]], trees[i]) > 0:
                    temp = stack.pop()
                    visited[temp] = False # 弹出栈的元素，应该取消标记
            stack.append(i)
            visited[i] = True
        
        # 找下凸包
        size = len(stack)
        for i in range(len(trees)-2, -1, -1):
            if visited[i]:
                continue
            # 下凸包这里 不能把之前的上凸包保存的点弹出去，所以应该是 > size
            while len(stack) >= size and \
                    self.cross(trees[stack[-2]], trees[stack[-1]], trees[i]) > 0:
                    temp = stack.pop()
                    visited[temp] = False
            
            stack.append(i)
            visited[i] = True
        
        res = [trees[i] for i in set(stack)]
        return res
        
        
    def cross(self, p, q, r):
        """
        向量的叉乘的方向，符合右手法则，也可以判断斜率变化
        """
        edge_0 = [q[0]-p[0], q[1]-p[1]]
        edge_1 = [r[0]-p[0], r[1]-p[1]]
        
        return edge_0[1] * edge_1[0] - edge_1[1] * edge_0[0]

587. 安装栅栏

法1 凸包问题 （Andrew 算法）

法1 凸包问题（Andrew 算法）