题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1392
这里介绍一种求凸包的算法：Graham。（相对于其它人的解释可能会有一些出入，但大体都属于这个算法的思想，同样可以解决凸包问题）
相对于包裹法的n*m时间，Graham算法在时间上有很大的提升，只要n*log(n)时间就够了。它的基本思想如下：
1、首先，把所有的点按照y最小优先，其次x小的优先排序
2、维护一个栈，用向量的叉积来判断新插入的点跟栈顶的点哪个在外围，如果栈顶的点在当前插入的点的左边，那么把栈顶的这个元素弹出，弹出之后不能继续插入下一个点，要继续判断当前插入点跟弹出之后的栈顶的点的位置关系，当当前插入的点在栈顶的那个点的左边时，则可以将要插入的点压到栈中，进入下一个点。
对于这题，最后要计算的是凸包的边长，所以最后别忘了加上最后一个点到第一个点的距离。还有只有一个点和两个点的情况时要进行特判。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = ;
struct point
{
double x,y;
point(double x = ,double y = ):x(x),y(y) {}
friend point operator + (point p1,point p2)
{
return point(p1.x+p2.x,p1.y+p2.y);
}
friend point operator - (point p1,point p2)
{
return point(p1.x-p2.x,p1.y-p2.y);
} }p[maxn],res[maxn];
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
double dot(point p1,point p2)
{
return p1.x*p2.y - p2.x*p1.y;
}
bool cmp(point p1,point p2)
{
if(p1.y == p2.y) return p1.x < p2.x;
return p1.y < p2.y;
}
int graham(point* p,int n,point* res)
{
sort(p,p+n,cmp);
res[] = p[];
res[] = p[];
// res[2] = p[2];
int top = ,len;
for(int i = ;i < n;++i)
{
while(top && dot(p[i]-res[top-],res[top]-res[top-]) >= ) top--;
res[++top] = p[i];
}
len = top;
for(int i = n-;i >= ;--i)
{
while(top != len && dot(p[i]-res[top-],res[top]-res[top-]) >= ) top--;
res[++top] = p[i];
}
return top;
} int main()
{
// freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n),n)
{
for(int i = ;i < n;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(n == )
{
printf("0.00\n");
continue;
}
if(n == )
{
printf("%.2lf\n",dis(p[],p[]));
continue;
}
int m = graham(p,n,res);
double tot = ;
for(int i = ;i <= m;++i)
tot += dis(res[i-],res[i]);
printf("%.2lf\n",tot);
}
return ;
}