力扣每日一题2022-04-23困难题：安装栅栏

安装栅栏

• • 题目描述
  • 思路
  • • Jarvis算法
    • • Python实现
      • Java实现

---

题目描述

安装栅栏

---

思路 Jarvis算法

首先必须要从凸包的某个点开始，假定从给定点集中最左边的点开始，例如最左边的点为P1。然后选择P2点，使得其余所有点都在向量P1P2的左侧或右侧，每次选择左侧，需要比较所有点以P1为原点的极坐标角度。然后以P2点为原点，重复上述步骤，依次找到P3P4P5…。
对于确定点的对于向量的左右关系，可以用如下方法确定：
左右方向是相对前进方向的，只要指定了前进方向就知道左右。因此，点在直线的左右侧可以用矢量来判断。
平面上三个点A(x1, y1)，B(x2, y2)，C(x3, y3)的面积为：S(A, B, C) = (x1-x3)(y2-y3) + (x2-x3)(y1-y3)。当ABC三点逆时针时S为正，当ABC三点顺时针时S为负。假定A为矢量起点，B为矢量终点，C为要判断的点，则有：

• S(A, B, C)为正数，C在矢量AB的左侧；
• S(A, B, C)为负数，C在矢量AB的右侧；
• S(A, B, C)为0，C在直线AB上。

Python实现

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        n = len(trees)
        if n < 4:
            return trees

        leftMost = 0
        for i, tree in enumerate(trees):
            if tree[0] < trees[leftMost][0]:
                leftMost = i

        ans = []
        vis = [False] * n
        p = leftMost
        while True:
            q = (p + 1) % n
            for r, tree in enumerate(trees):
                # // 如果 r 在 pq 的右侧，则 q = r
                if cross(trees[p], trees[q], tree) < 0:
                    q = r
            # 是否存在点 i, 使得 p q i 在同一条直线上
            for i, b in enumerate(vis):
                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:
                    ans.append(trees[i])
                    vis[i] = True
            if not vis[q]:
                ans.append(trees[q])
                vis[q] = True
            p = q
            if p == leftMost:
                break
        return ans

Java实现

class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        int leftMost = 0;
        for (int i = 0; i < n; i++) {
            if (trees[i][0] < trees[leftMost][0]) {
                leftMost = i;
            }
        }

        List<int[]> res = new ArrayList<int[]>();
        boolean[] visit = new boolean[n];
        int p = leftMost;
        do {
            int q = (p + 1) % n;
            for (int r = 0; r < n; r++) {
                /* 如果 r 在 pq 的右侧，则 q = r */ 
                if (cross(trees[p], trees[q], trees[r]) < 0) {
                    q = r;
                }
            }
            /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
            for (int i = 0; i < n; i++) {
                if (visit[i] || i == p || i == q) {
                    continue;
                }
                if (cross(trees[p], trees[q], trees[i]) == 0) {
                    res.add(trees[i]);
                    visit[i] = true;
                }
            }
            if  (!visit[q]) {
                res.add(trees[q]);
                visit[q] = true;
            }
            p = q;
        } while (p != leftMost);
        return res.toArray(new int[][]{});
    }

    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
}