587.安装栅栏

链接：587.安装栅栏
难度：Hard
标签：几何、数组、数学
简介：在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

题解 1 - cpp

• 编辑时间：2022-04-23
• 执行用时：32ms
• 内存消耗：19.3MB
• 编程语言：cpp
• 解法介绍：andrew 凸包算法。

class Solution {
   public:
    int cross(vector<int> &a, vector<int> &b, vector<int> &c) {
        int x1 = a[0] - b[0], y1 = a[1] - b[1];
        int x2 = c[0] - b[0], y2 = c[1] - b[1];
        return x1 * y2 - x2 * y1;
    }
    vector<vector<int>> outerTrees(vector<vector<int>> &trees) {
        int n = trees.size();
        if (n <= 3) return trees;
        sort(trees.begin(), trees.end(),
             [&](vector<int> &a, vector<int> &b) -> bool {
                 if (a[0] == b[0]) return a[1] < b[1];
                 return a[0] < b[0];
             });
        vector<int> list, used(n, 0);
        for (int i = 0; i < n; i++) {
            while (list.size() > 1 &&
                   cross(trees[list[list.size() - 2]],
                         trees[list[list.size() - 1]], trees[i]) < 0) {
                used[list.back()] = 0;
                list.pop_back();
            }
            list.push_back(i);
            used[i] = 1;
        }
        int size = list.size();
        used[0] = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (used[i]) continue;
            while (list.size() > size &&
                   cross(trees[list[list.size() - 2]],
                         trees[list[list.size() - 1]], trees[i]) < 0) {
                list.pop_back();
            }
            list.push_back(i);
        }
        list.pop_back();
        vector<vector<int>> ans;
        for (auto &idx : list) ans.emplace_back(trees[idx]);
        return ans;
    }
};