凸包.cpp

数值分析中常用的几种算法的实现

//求凸包
#include<stdio.h>
#include<math.h>
struct ppp
{
	double x;
	double y;
};
void swap(ppp &a, ppp &b)
{
	ppp temp;
	temp=a;
	a=b;
	b=temp;
	return;
}
double dis(ppp a,ppp b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double multi(ppp a1,ppp a2,ppp a3,ppp a4)
{
	double x1,x2,y1,y2;
	x1=a2.x-a1.x;
	y1=a2.y-a1.y;
	x2=a4.x-a3.x;
	y2=a4.y-a3.y;
	return (x1*y2-x2*y1);
}
int main()
{
	int n,i,j,k,top;
	double min,minx,sum;
	double angle[200],temp;
	ppp point[200],stack[200];
	freopen("test.txt","r",stdin);
	while(1)
	{
		scanf("%d",&n);
		if(n==0)
			return 0;
		for(i=0;i<n;i++)
			scanf("%lf%lf",&point[i].x,&point[i].y);
		if(n==1)
		{
			printf("0.00\n");
			continue;
		}
		else if(n==2)
		{
			printf("%.2lf\n",2*dis(point[0],point[1]));
			continue;
		}
		min=100000;
		minx=100000;
		for(i=0;i<n;i++)
		{
			if(min>point[i].y)
			{
				min=point[i].y;
				minx=point[i].x;
				k=i;
			}
		}
		swap(point[0],point[k]);
		for(i=1;i<n;i++)
			angle[i]=(point[i].x-point[0].x)/dis(point[i],point[0]);
		for(i=1;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(angle[i]<angle[j]||(angle[i]==angle[j]&&point[i].x>point[j].x))
				{
					swap(point[i],point[j]);
					temp=angle[i];
					angle[i]=angle[j];
					angle[j]=temp;
				}
			}
		}
		stack[0]=point[0];
		stack[1]=point[1];
		stack[2]=point[2];
		top=2;
		for(i=3;i<n;i++)
		{
			while(multi(stack[top-1],stack[top],stack[top],point[i])<=0)
				top--;
			top++;
			stack[top]=point[i];
		}
		sum=0;
		for(i=0;i<=top;i++)
			sum+=dis(stack[i],stack[(i+1)%(top+1)]);
		printf("%.2lf\n",sum);
	}
}