G52 凸包 Andrew算法【计算几何】

Andrew算法（推荐）:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Point
{
    double x,y;
    Point(){}
    Point(double a,double b):x(a),y(b){}
    void input(){scanf("%lf%lf",&x,&y);} 
    friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
    friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};}
    friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;}
    friend double dis(Point a,Point b){Point p=a-b;return sqrt(p.x*p.x+p.y*p.y);}
};
Point P[N],sta[N];int n,top;

void Andrew()
{
    sort(P+1,P+n+1);
    top=0;
    for(int i=1;i<=n;i++)
    {
        while( top>1 && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--;
        sta[++top]=P[i];
    }
    int t=top;
    for(int i=n-1;i>=1;i--)
    {
        while( top>t && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--;
        sta[++top]=P[i];
    }
    n=top-1;//注意：sta[1]和sta[top]都是P[1]   
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)P[i].input();
    Andrew();
    double ans=0.0;
    for(int i=1;i<n;i++) ans+= dis(sta[i],sta[i+1]);
    ans+=dis(sta[n],sta[1]);
    printf("%0.2lf\n",ans);
    return 0;
}

Graham扫描法:

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
struct point{
    double x,y;
    double ang,dis;
}p[N];
bool cmp(point p1,point p2){
    if(p1.ang==p2.ang)return p1.dis<p2.dis;
    else return p1.ang<p2.ang;
}
bool rturn(point p1,point p2,point p3){
    double x=p1.x,x2=p2.x,x3=p3.x,y=p1.y,y2=p2.y,y3=p3.y;
    double v1x=x2-x,v1y=y2-y,v2x=x3-x2,v2y=y3-y2;
    double cross=v1x*v2y-v1y*v2x;
    return cross<0;
}
double dis(point p1,point p2){
    double x=p1.x-p2.x,y=p1.y-p2.y;
    return sqrt(x*x+y*y);
}
int st[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
        if((p[1].y>p[i].y)||(p[1].y==p[i].y&&p[1].x>p[i].x))swap(p[1],p[i]);
    }
    for(int i=2;i<=n;i++){
        p[i].x-=p[1].x,p[i].y-=p[1].y;
        p[i].ang=atan2(p[i].y,p[i].x);
        p[i].dis=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
    }
    p[1].x=p[1].y=0;
    sort(p+2,p+1+n,cmp);
    int t=1;st[t]=1;
    for(int i=2;i<=n;i++){
        while(t>=2&&rturn(p[st[t-1]],p[st[t]],p[i]))t--;
        st[++t]=i;
    }
    double ans=dis(p[st[1]],p[st[t]]);
    for(int i=2;i<=t;i++){
        ans+=dis(p[st[i]],p[st[i-1]]);
    }
    cout<<fixed<<setprecision(2)<<ans;
    cout << endl;
    return 0;
}