587. 安装栅栏

在一个二维的花园中，有一些用 (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]]
解释:

即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

1. 所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
2. 输入的整数在 0 到 100 之间。
3. 花园至少有一棵树。
4. 所有树的坐标都是不同的。
5. 输入的点没有顺序。输出顺序也没有要求。

 1 vector<int> start; // 凸包起点坐标
 2 // 排序找第一个点,先按y轴升序,如果y轴相等,则按x轴升序
 3 inline bool cmp1(const vector<int> &a, const vector<int> &b) {
 4     // y轴相等,则按照x轴升序排序
 5     if (a[1] == b[1]) {
 6         return a[0] < b[0];
 7     } else {
 8         return a[1] < b[1];
 9     }
10 }
11 // 两条边（向量）的叉积, 向量ab与向量ac的叉积
12 inline  double cross(const vector<int> &a, const vector<int> &b, const vector<int> &c) { // 计算叉积
13     return ((b[0] - a[0]) * (c[1] - a[1]) * 1.0 - (b[1] - a[1]) * (c[0] - a[0]));
14 }
15 // 计算线段ab的长度
16 inline  double distance(const vector<int> & a, const vector<int> & b) {
17     return (a[0] - b[0]) * (a[0] - b[0]) * 1.0 + (a[1] - b[1]) * (a[1] - b[1]);
18 }
19 // 按照夹角从小到大排序,夹角相同时按照x轴升序排序
20 inline bool cmp2(const vector<int> &a, const vector<int> &b) {
21     int diff = cross(start, a, b);
22     if (diff == 0) {
23         return distance(start, a) < distance(start, b);
24     } else {
25         return diff > 0;
26     }
27 }
28 class Solution {
29 public:
30     vector<vector<int>> outerTrees(vector<vector<int>> &trees) {
31         int n = trees.size();
32         if (n < 4) {
33             return trees;
34         }
35         // 对trees按y轴升序排序
36         sort(trees.begin(), trees.end(), cmp1);
37         start = trees[0];
38         /* 除凸包起点外剩余点按照极坐标的角度大小进行排序 */
39         sort(trees.begin() + 1, trees.end(), cmp2);
40         /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
41         int r = n - 1;
42         while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) == 0) {
43             r--;
44         }
45         for (int l = r + 1, h = n - 1; l < h; l++, h--) {
46             swap(trees[l], trees[h]);
47         }
48         stack<int> st; // 存储点在trees中的下标索引
49         st.emplace(0);
50         st.emplace(1);
51         for (int i = 2; i < n; i++) {
52             int top = st.top();
53             st.pop();
54             /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
55             while (!st.empty() && cross(trees[st.top()], trees[top], trees[i]) < 0) {
56                 top = st.top();
57                 st.pop();
58             }
59             st.emplace(top);
60             st.emplace(i);
61         }
62 
63         vector<vector<int>> res;
64         while (!st.empty()) {
65             res.emplace_back(trees[st.top()]);
66             st.pop();
67         }
68         return res;
69     }
70 };