[数据结构与算法]二维凸包算法（Andrew算法）

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]

    bool tmp(vector<int> &a, vector<int> &b)
{
    if (a[0]==b[0]) return a[1]<b[1];
    else return a[0]<b[0];
}
class Solution {

//ABXAC
int cross(vector<int>&a,vector<int>&b,vector<int>&c){
    return (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1]);
}
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
    sort(trees.begin(),trees.end(),tmp);
    int n = trees.size();
    vector<int>q(n+2,0);
    vector<bool>hasVisit(n,false);
    int nums = 0;
    q[++nums] = 0;
    for(int i=1;i<n;i++){
         vector<int> c = trees[i];
         while(nums>1){
         if(cross(trees[q[nums-1]],trees[q[nums]],c)>0){
                hasVisit[q[nums--]] = false;
            }else break;
          }
          q[++nums]=i;
          hasVisit[i]=true;
       }

       for(int i=n-1;i>=0;i--){
         if(hasVisit[i]) continue;
        vector<int> c = trees[i];
         while(nums>1){
         if(cross(trees[q[nums-1]],trees[q[nums]],c)>0){
                hasVisit[q[nums--]] = false;
            }else break;
          }
          q[++nums]=i;
          hasVisit[i]=true;
       }
    vector<vector<int>> res(nums-1);
    for (int i = 1; i < nums; ++i) res[i-1] = trees[q[i]];
    return res;
    }
};

阅读世界，共赴山海

423全民读书节，邀你共读