农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
格式
PROGRAM NAME: fc
INPUT FORMAT
输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。
OUTPUT FORMAT
输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。
SAMPLE INPUT (file fc.in)
4
4 8
4 12
5 9.3
7 8
SAMPLE OUTPUT (file fc.out)
12.00
分析：赤裸裸的凸包问题。参考资料
【参考程序】：
/*
ID: XIONGNA1
PROG: fc
LANG: C++
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
struct point
{
double x,y;
} stack[10001],p[10001],ST;
int n,top;
double dis(point a1,point a2)
{
double s=pow((a1.x-a2.x),2.0)+pow((a1.y-a2.y),2.0);
return sqrt(s);
}
double chaji(point a1,point a2,point a0)
{
point x1,x2;
x1.x=a1.x-a0.x; x1.y=a1.y-a0.y;
x2.x=a2.x-a0.x; x2.y=a2.y-a0.y;
return (x1.x*x2.y)-(x2.x*x1.y);
}
int cmp(const void *s,const void *t)
{
point i=*(point *)s,j=*(point *)t;
double m=chaji(i,j,ST);
if (m<0) return 1;
if (m==0 && dis(i,ST)<dis(j,ST)) return 1;
return -1;
}
void init()
{
double mx=-0xFFFFFFF; int k;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if (p[i].x>mx)
{
mx=p[i].x; ST=p[i];
k=i;
}
}
p[k]=p[n]; n--;
qsort(p+1,n,sizeof(point),cmp);
}
void graham()
{
double m;
stack[0]=ST; stack[top=1]=p[1];
for (int i=2;i<=n;i++)
{
stack[++top]=p[i];
m=chaji(stack[top],stack[top-2],stack[top-1]);
while (m<0)
{
stack[top-1]=stack[top];
top--;
m=chaji(stack[top],stack[top-2],stack[top-1]);
}
}
}
void cout_ans()
{
double ans=0.0;
for (int i=1;i<=top;i++)
ans+=dis(stack[i-1],stack[i]);
ans+=dis(stack[top],stack[0]);
printf("%.2lf\n",ans);
}
int main()
{
freopen("fc.in","r",stdin);
freopen("fc.out","w",stdout);
init();
graham();
cout_ans();
return 0;
}