Surround the Trees

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7672    Accepted Submission(s): 2936

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?

The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees.

9 
12 7 
24 9 
30 5 
41 9 
80 7 
50 87 
22 9 
45 1 
50 7 
0 

243.06

/*
HDOJ 1392 求凸包的周长

极角排序的时候用的是向量的叉乘，判断两条直线的偏转角大小！ 
用叉乘法，分别将两点：B C与最低点A连接,若AB×AC<0,则B的极角大于C。向下拐的 
等于0的，也就是A,B,C共线，则令离A远的点极角大。
特别的，若入栈使没有拐弯过，即所有点共线，要除2。
n=1,2单独考虑 
*/
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

struct point{
	int x,y;
};
int n,top;
point s[101],p[101];

double multi(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
  
double dis(point a, point b)
{
    return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));//要加double 
}

int cmp(const void *a,const void *b)
{
	point c=*(point *)a;
	point d=*(point *)b;
	double k=multi(p[0],c,d);
	if(k<0||k==0&&dis(c,p[0])>dis(d,p[0]))//排序  调换 
		return 1;
	return -1;
} 

void convex()
{
	int i;
	point t;
	
	for(i=1;i<n;i++)//寻找第一个点 y最小,y相同x最小 
	{
		if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
		{
			t=p[i];
			p[i]=p[0];
			p[0]=t;
		}
	}
	
	qsort(p+1,n-1,sizeof(p[0]),cmp);//对n-1个点按极角排序 第一个点除外 
	
	s[0]=p[0];
	s[1]=p[1];
	s[2]=p[2];
	top=2;
	
	for(i=3;i<n;i++)
	{
		while(top>=2&&multi(s[top-1],s[top],p[i])<=0)
		//新加入的点，若与栈里2个点 极角<0,则顺时针方向，不符合，出栈 
			top--;
		s[++top]=p[i];//加入当前点 
	}
}

int main()
{
	int i;
	double sum;
	
	//freopen("test.txt","r",stdin);
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		if(n==1)// 处理n=1，2情况 
		{
			printf("0.00\n");
			continue;
		}
		else if(n==2)
		{
			printf("%.2lf\n",dis(p[0],p[1]));
			continue;
		}
		
		convex();//凸包 
		sum=0;
		for(i=0;i<top;i++)//求和距离 
		{
			sum+=dis(s[i],s[i+1]);
		}
		sum+=dis(s[top],s[0]);//最后一个点和第一个点 
		printf("%.2lf\n",sum);
	}
	return 0;
}