1113.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#define NMAX 1054
#define INF 1000000001
#define DIFF 1000
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
typedef struct
{
	long x,y;
}data;

data p[NMAX];
int st[NMAX];
int n,l;
const double pi=3.1415926;
double dis(data a,data b)
{
	return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dis2(data a,data b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void swap(data &a,data &b)
{
	data t;
	t=a;
	a=b;
	b=t;
}
void findmin()
{
	int i;
	for(i=1;i<n;i++)
	{
		if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[0].x>p[i].x))
			swap(p[0],p[i]);
	}
}
long cross(data p2,data p1,data p0)
{
	return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y);
}
int cmp(const void *a,const void *b)
{
	long t=cross(*(data*)a,*(data*)b,p[0]);
	if(t==0)
	{
		t=dis2((*(data*)a),p[0])-dis2((*(data*)b),p[0]);
		if(t>0)
			return 1;
		else if (t<0)
			return -1;
		else
			return 0;
	}
	else
	{
		if(t>0)
			return -1;
		else
			return 1;
	}
}
double round(double l)
{
	double t=floor(l);
	if(l-t>=0.666666666)
		return ceil(l);
	else
		return t;
}
void solve()
{
	findmin();
	qsort(p+1,n-1,sizeof(data),cmp);
	int cp=0;
	int i;
	for(i=0;i<3;i++)
		st[i]=i;
	cp=2;
	for(i=3;i<n;i++)
	{
		while(cross(p[i],p[st[cp]],p[st[cp-1]])>0)
		{
			cp--;
		}
		cp++;
		st[cp]=i;
	}
	double ans=0;
	for(i=0;i<cp;i++)
	{
		ans+=dis(p[st[i]],p[st[i+1]]);
	}
	ans+=dis(p[st[0]],p[st[cp]]);
	ans+=2*pi*l;
//	ans=round(ans);
	printf("%.0lf\n",ans);
	

}

int main()
{

	int i;
//	while(1)

		scanf("%d%d",&n,&l);
//		if(!n)
//			break;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&p[i].x,&p[i].y);
			p[i].x+=DIFF;
			p[i].y+=DIFF;
		}
		solve();
		



	return 1;
}