凸包算法-- Andrew 算法

class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        /* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
        Arrays.sort(trees, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[n];
        /* list[0] 需要入栈两次，不进行标记 */
        list.add(0);
        /* 求出凸包的下半部分 */
        for (int i = 1; i < n; i++) {
            while (list.size() > 1 && cross(trees[list.get(list.size() - 2)], trees[list.get(list.size() - 1)], trees[i]) < 0) {
                used[list.get(list.size() - 1)] = false;
                list.remove(list.size() - 1);
            }
            used[i] = true;
            list.add(i);
        }
        int m = list.size();
        /* 求出凸包的上半部分 */
        for (int i = n - 2; i >= 0; i--) {
            if (!used[i]) {
                while (list.size() > m && cross(trees[list.get(list.size() - 2)], trees[list.get(list.size() - 1)], trees[i]) < 0) {
                    used[list.get(list.size() - 1)] = false;
                    list.remove(list.size() - 1);
                }
                used[i] = true;
                list.add(i);
            }
        }
        /* list[0] 同时参与凸包的上半部分检测，因此需去掉重复的 list[0] */
        list.remove(list.size() - 1);
        int size = list.size();
        int[][] res = new int[size][2];
        for (int i = 0; i < size; i++) {
            res[i] = trees[list.get(i)];
        }
        return res;
    }
    /*比较斜率是否为左拐,大于0说明是左拐
     * (x2-x1)/(y2-y1) - (x3-x2)/(y3-y2) = (x2-x1)(y3-y2) - (x3-x2)(y2-y1)
     * */
    private 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]);
    }
}

587