凸包

模版题： http://acm.hdu.edu.cn/showproblem.php?pid=1392

#include<bits/stdc++.h>
using namespace std;
const int M=1e3+3;
struct tu{
    double x,y;
    tu friend operator -(tu a,tu b){
        return {a.x-b.x,a.y-b.y};
    }
}p[M],s[M];
double X(tu a,tu b){
    return a.x*b.y-a.y*b.x;
}
double dis(tu a,tu b){
    a=a-b;
    return sqrt(a.x*a.x+a.y*a.y);
}
bool cmp(tu a,tu b){
    int x=X(a-p[1],b-p[1]);
    if(x>0||x==0&&dis(a,p[1])<dis(b,p[1]))
        return 1;
    return 0;
}

int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=1;i<=n;i++)
            cin>>p[i].x>>p[i].y;


        int k=1;
        if(n==1){
            printf("0.00\n");
            continue;
        }
        else if(n==2){
            printf("%.2lf\n",dis(p[1],p[2]));
            continue;
        }
        for(int i=2;i<=n;i++)
            if(p[i].y<p[k].y||p[i].y==p[k].y&&p[i].x<p[k].x)
                k=i;
        swap(p[1],p[k]);
        sort(p+2,p+1+n,cmp);
        s[1]=p[1],s[2]=p[2];
        int tot=2;
        for(int i=3;i<=n;i++){
            while(tot>=2&&X(s[tot]-s[tot-1],p[i]-s[tot-1])<=0)
                tot--;
            s[++tot]=p[i];
        }

        double ans=dis(s[1],s[tot]);
       /// cout<<ans<<endl;
        for(int i=2;i<=tot;i++)
            ans+=dis(s[i],s[i-1]);
        printf("%.2lf\n",ans);
    }
    return 0;
}

View Code