幾何：凸包

凸包（Convex Hull）是一個計算幾何（圖形學）中的概

念。在一個實數向量空間V中，對于給定集合X，所有包

含X的凸集的交集S被稱為X的凸包。X的凸包可以用X内所

有點(X1，…Xn)的凸組合來構造.在二維歐幾裡得空間中，

凸包可想象為一條剛好包著所有點的橡皮圈。用不嚴謹

的話來講，給定二維平面上的點集，凸包就是将最外層

的點連接配接起來構成的凸多邊形，它能包含點集中所有的

點。

做法：

第一步：找到最下邊的點，如果有多個點縱坐标相同的點都在最下方，則選取最左邊的，記為點A。這一步隻需要掃描一遍所有的點即可，時間複雜度為 O(n)

第二步：将所有的點按照 AP_i 的極角大小進行排序，極角相同的按照到點A的距離排序。時間複雜度為 O(nlogn)

第三步：維護一個棧，以儲存目前的凸包。按第二步中排序得到的結果，依次将點加入到棧中，如果目前點與棧頂的兩個點不是“向左轉”的，就表明目前棧頂的點并不在凸包上，而我們需要将其彈出棧，重複這一個過程直到目前點與棧頂的兩個點是“向左轉”的。這一步的時間複雜度為 O(n)

**求凸包

/模闆說明：n為所有點的個數，top為棧頂，P[]為所有點，下标為0n-1，result[]為凸包上的點，下标為0top，包含凸包邊上的點,Error:有重複點/

**

int n, top;
Point P[10005], result[10005];
bool cmp(Point A, Point B)
{
    double ans = Cross(A - P[0], B - P[0]);
    if (dcmp(ans) == 0)
        return dcmp(Distance(P[0], A) - Distance(P[0], B)) < 0;
    else
        return ans > 0;
}
void Graham()//Graham凸包掃描算法
{
    for (int i = 1; i < n; i++)//尋找起點
        if (P[i].y < P[0].y || (dcmp(P[i].y - P[0].y) == 0 && P[i].x < P[0].x))
            swap(P[i], P[0]);
    sort(P + 1, P + n, cmp);//極角排序，中心為起點
    result[0] = P[0];
    result[1] = P[1];
    top = 1;
    for (int i = 2; i < n; i++)
    {
        while (top >= 1 && Cross(result[top] - result[top - 1], P[i] - result[top - 1]) < 0)
            top--;
        result[++top] = P[i];
    }
}
           

Andrew算法 (複雜度nlogn)

Andrew算法是一種基于水準序的算法，是Graham-Scan算法的一種變體，性能也更優, 隻不過是掃描之前做的處理不同.

1:将所有的點按x坐标從小到大排序，橫坐标相同則按y坐标從小到大排.

2:将p[1]和p[2]加入凸包，然後從p[3]開始判斷，判斷方式與Graham-Scan算法中一緻.

3:将所有的點掃描一遍以後，我們就得到一個“下凸包”

4:同理，我們再從p[n-1]開始(p[n]在上面判過就不用判了,但是p[1]要判,最後再把len-1就好了)，反着再掃一遍，得到“上凸包”

5:上凸包和下凸包合在一起就是完整的凸包.

struct Point;
typedef Point Vector;

struct Point{
    double x,y;
    Point(){}
    Point(double a, double b):x(a),y(b){}
    double len(){return sqrt(x*x+y*y);}
    double disToPoint(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));}
    void read(){scanf("%lf%lf",&x,&y);}
    Point operator+(Vector v){return {x+v.x,y+v.y};}
    Vector operator-(Point p){return {x-p.x,y-p.y};}
    double operator^(Vector v){return x*v.y-y*v.x;}//叉乘
    double operator*(Vector v){return x*v.x+y*v.y;}//點乘
    Vector operator*(double d){return {x*d,y*d};}
    Vector operator/(double d){return {x/d,y/d};}
    bool operator==(Point p){return cmp(x,p.x)==0&&cmp(y,p.y)==0;}
    bool operator<(Point p){if(cmp(x,p.x)==0) return y<p.y;return x<p.x;}
};
Point p[MAXN];
Point stk[MAXN];
int Andrew(){//點的存儲位置[1,n]
    sort(p+1,p+1+n);
    int len=0;
    for (int i=1;i<=n;i++){
        while (len>1&&sgn((stk[len]-stk[len-1])^(p[i]-stk[len-1]))<0) len--;
        stk[++len]=p[i];
    }
    int k=len;
    for (int i=n-1;i>=1;i--){
        while (len>k&&sgn((stk[len]-stk[len-1])^(p[i]-stk[len-1]))<0) len--;
        stk[++len]=p[i];
    }
    len--;
    return len;
}