二维凸包模板 luoguP2742

题目：给定一些点，求能把所有这些点包含在内的最小的凸多边形

解法：算法竞赛入门到进阶P283的Andrew算法

（1）把所有这些点按照横坐标从小到大排序，如果x相同，按照y从小到大排序

（2）从左到右扫描所有点，求下凸包。每到达一个点时判断，如果新点在下凸包左前方（向量判断），加入下凸包，否则回溯（删除最近加入的，知道这个新点在下凸包左边，并加入凸包）

（3）同理求上凸包

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int sgn(double x){
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}
struct Point{
    double x,y;
    Point(double X=0,double Y=0){
        x=X;
        y=Y;
    }
    Point operator +(Point B){
        return Point(x+B.x,y+B.y);
    }
    Point operator -(Point B){
        return Point(x-B.x,y-B.y);
    }
    Point operator *(double k){
        return Point(x*k,y*k);
    }
    Point operator /(double k){
        return Point(x/k,y/k);
    }
    bool operator ==(Point B){
        return sgn(x-B.x)==0&&sgn(y-B.y)==0;
    }
    bool operator <(Point B){
        return sgn(x-B.x)<0||(sgn(x-B.x)==0&&sgn(y-B.y<0));
    }
}; 
typedef Point Vector;
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
double Distance(Point A,Point B){
    return hypot(A.x-B.x,A.y-B.y);
}
int Convex_hull(Point *p,int n,Point *ch){
    sort(p,p+n);
    n=unique(p,p+n)-p;
    int v=0;
    for(int i=0;i<n;i++){
        while(v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
        v--;
        ch[v++]=p[i];
    }
    int j=v;
    for(int i=n-2;i>=0;i--){
        while(v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
        v--;
        ch[v++]=p[i];
    }
    if(n>1)v--;
    return v;
}
Point p[11000],ch[11000];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>p[i].x>>p[i].y;
    int v=Convex_hull(p,n,ch);
    double ans=0;
    if(v==1)ans=0;
    else if(v==2)ans=Distance(ch[0],ch[1]);
    else{
        for(int i=0;i<v;i++)
            ans+=Distance(ch[i],ch[(i+1)%v]);
        printf("%.2lf\n",ans);
    } 
    return 0;
}