# Convex Hull 凸包演算法
- 使用 `vector<int>` 來記錄點 `(x,y)`

    // positive if clockwise
    // negative if counter clockwise
    int orientation(vector<int> &p, vector<int> &q, vector<int> &r) {
        int pqx = q[0]-p[0], pqy = q[1]-p[1];
        int qrx = r[0]-q[0], qry = r[1]-q[1];
        return pqy*qrx - pqx*qry;
    }
    int distance(vector<int> &p, vector<int> &q) {
        return (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1]);
    }

- 1.Javis' March
- 1.先任意找凸包上的一個點，這裡取 x 最小的點
- 2.逆時針把凸包上的點找出
- 總時間複雜度 O(NC) ，其中 C 為凸包頂點數
- 以下不考慮共線問題，需另外處理

    vector<vector<int>> Javis(vector<vector<int>>& points) {
        int n = points.size();
        if(n < 4) return points;
        vector<vector<int>> ans;
        
        int start = 0;
        for(int i=0;i<n;i++)    if(points[i][0]<points[start][0])   start=i;
        int p = start;
        
        while(1){
            int q = (p+1) % n;
            for(int i=0;i<n;i++)
                if(orientation(points[p],points[q],points[i])<0)
                    q = i;
            ans.push_back(points[q]);
            p = q;
            if(p==start)    break;
        }
        return ans;
    }

- 2.Granham Scan
- 1.先將所有點依照逆時針順序排好
- 2.再來做繞行一圈的動作，每三個點判斷
- 總時間複雜度 O(NlogN) ，主要取決於排序的時間

    vector<vector<int>> Granham(vector<vector<int>>& points) {
        int n = points.size();
        if(n < 4) return points;
        
        // pivot 取 y 最小的點，當作排序基準
        vector<int> pivot = points[0];
        for(int i=0;i<n;i++)    if(points[i][1] < pivot[1])    pivot = points[i];
        
        // 先把 points 按照角度排序，若角度相等照長度小到大
        sort(points.begin(),points.end(),[&](vector<int> p, vector<int> q){
            if(p[0]==pivot[0]&&p[1]==pivot[1])      return true;
            if(q[0]==pivot[0]&&q[1]==pivot[1])      return false;
            if(orientation(pivot, p, q)==0)         return distance(pivot, p) < distance(pivot, q);
            else                                    return orientation(pivot, p, q) < 0;
        });
        // 最後一條線照長度大到小
        int t = n-2;
        while(t>0 && orientation(pivot, points[t], points[n-1])==0) t--;
        for(int l=t+1, r=n-1;l<r;l++,r--)     swap(points[l],points[r]);
        
        // Graham Scan，每三個點判斷順逆時針
        vector<vector<int>> ans = {points[0], points[1]};
        for(int j=2;j<n;j++){
            while(ans.size()>=2 && orientation(ans[ans.size()-2], ans[ans.size()-1], points[j]) > 0)
                ans.pop_back();
            ans.push_back(points[j]);
        }
        return ans;
    }

- 3.Monotone Chain
- 1.先把點照 x 排序
- 2.先找出上凸包，再找出下凸包
- 總時間複雜度 O(NlogN) ，主要取決於排序的時間

    vector<vector<int>> MonotoneChain(vector<vector<int>>& points) {
        int n = points.size();
        if(n < 4) return points;
        sort(points.begin(),points.end());        
        vector<vector<int>> ans;
        
        for(int i=0;i<n;i++){       // upper convex hull
            while (ans.size()>=2 && orientation(ans[ans.size()-2], ans[ans.size()-1], points[i]) < 0)
                ans.pop_back();
            ans.push_back(points[i]);
        }
        if (ans.size() == n) return ans;    // one side is enough
        ans.pop_back();
        for(int i=n-1;i>=0;i--){    // lower convex hull
            while (ans.size()>=2 && orientation(ans[ans.size()-2], ans[ans.size()-1], points[i]) < 0)
                ans.pop_back();
            ans.push_back(points[i]);
        }
        ans.pop_back();
        return ans;
    }

- 4.其他還有 divide and conquer ，線上維護等方法