587. 安装栅栏(凸包问题)
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]] 解释:
即使树都在一条直线上，你也需要先用绳子包围它们。
注意:
- 所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
- 输入的整数在 0 到 100 之间。
- 花园至少有一棵树。
- 所有树的坐标都是不同的。
- 输入的点没有顺序。输出顺序也没有要求。
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 };