hdu-1392（二維凸包模闆）

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct
{
    double x;
    double y;
} POINT;
POINT result[102];//儲存凸包上的點，相當于所說的棧S
POINT a[102];
int n,top;
double Distance(POINT p1,POINT p2)//兩點間的距離
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double Multiply(POINT p1,POINT p2,POINT p3)//叉積
{
    return((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
}
bool cmp(POINT aa,POINT bb)//按點乘排序，cos=a*b/|a||b|
{
    int ax=aa.x-a[0].x;
    int ay=aa.y-a[0].y;
    int bx=bb.x-a[0].x;
    int by=bb.y-a[0].y;
    float cosa=ax/sqrt(ax*ax+ay*ay);
    float cosb=bx/sqrt(bx*bx+by*by);
    return cosa>cosb;
}
//尋找凸包的過程，p0,p1,p2..的尋找過程在下面main中進行了
void Tubao()
{
    int i;
    result[0].x=a[0].x;
    result[0].y=a[0].y;
    result[1].x=a[1].x;
    result[1].y=a[1].y;
    result[2].x=a[2].x;
    result[2].y=a[2].y;
    top=2;
    for(i=3; i<=n; i++)
    {
        while(Multiply(result[top-1],result[top],a[i])<=0&&top>=2)
            top--;
        result[top+1].x=a[i].x;
        result[top+1].y=a[i].y;
        top++;
    }
}
int main()
{
    int i,p;
    double px,py,len,temp;
    while(scanf("%d",&n)!=EOF,n)//
    {
        for(i=0; i<n; i++)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        if(n==1)
        {
            printf("0.00\n");
            continue;
        }
        else if(n==2)
        {
            printf("%.2lf\n",Distance(a[0],a[1]));
            continue;
        }
//這裡的目的好像是找出y坐标最小的點，之後把他定義為P0
        py=-1;
        for(i=0; i<n; i++)
        {
            if(py==-1||a[i].y<py)
            {
                px=a[i].x;
                py=a[i].y;
                p=i;
            }
            else if(a[i].y==py&&a[i].x<px)
            {
                px=a[i].x;
                py=a[i].y;
                p=i;
            }
        }
//swap(a[0],a[p])
        temp=a[0].x;
        a[0].x=a[p].x;
        a[p].x=temp;
        temp=a[0].y;
        a[0].y=a[p].y;
        a[p].y=temp;
        sort(a+1,a+n,cmp);
        a[n].x=a[0].x;
        a[n].y=a[0].y;
//調用tubao（）
        Tubao();
        len=0.0;
        for(i=0; i<top; i++)
            len=len+Distance(result[i],result[i+1]);
        printf("%.2lf\n",len);
    }
    return 0;
}