几何：凸包

凸包（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;
}