HDUJ 1392 Surround the Trees 凸包

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

    243.06

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

struct node
{
	double x,y;
}a[105],b[105];

double cmp(node n,node m)    //先比較X坐标，在比較Y坐标（从小到大）
{
	if(n.x != m.x)   
		return  n.x < m.x;
	else
		return  n.y < m.y;
}

double Cross(node a,node b,node c)     //计算叉积大小
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double dis(node a,node b)     //计算距离
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int CH(node* a,int n,node* b)
{
	sort(a,a+n,cmp);
	int m=0,i;
	for(i=0;i<n;i++)    //从左往右，选下边界
	{
		while(m > 1 && Cross(b[m-2],b[m-1],a[i]) < 0)
			m--;
		b[m++]=a[i];
	}


	int k=m;
	for(i=n-2;i>=0;i--)    //从右往左，选上边界
	{
		while(m > k && Cross(b[m-2],b[m-1],a[i]) < 0)
			m--;
		b[m++]=a[i];
	}
	
	if(n >1)  m--;
	return m;
}

int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0)   break;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));

		int i,j;
		for(i=0;i<n;i++)
		{
			cin>>a[i].x>>a[i].y;
		}
		
	//	cout<<CH(a,n,b)<<endl;     //输出所选点的总数
		if(n==1)   
			cout<<0.00<<endl;
		else  if(n==2)
			printf("%.2lf\n",dis(a[0],a[1]));	
		else
		{
			int m=CH(a,n,b);
			double s=0;
			for(i=1;i<m;i++)
				s+=dis(b[i-1],b[i]);
			s+=dis(b[0],b[m-1]);
			printf("%.2lf\n",s);
		}
	//	for(i=0;i<CH(a,n,b);i++)    //输出所选点的坐标
	//		cout<<b[i].x<<" "<<b[i].y<<endl;   

	}

	return 0;
}