2235555_ac_45ms_76k.cc

北大大牛代码 1240道题的原代码 超级权威

//Graham scan algorithm
//O(nlgn)
# include <stdio.h>
# include <math.h>
# include <algorithm>
# define MAX 1001
# define PI acos(-1)
using namespace std;

typedef int stack;
struct node
{
	int x, y;
}Q[MAX];

int n, L, low;
int lowx, lowy;
stack p, s[MAX];

bool cmp(struct node a,struct node b)
{
	if(a.x==lowx&&a.y==lowy)
		return 1;
	if(b.x==lowx&&b.y==lowy)
		return 0;
	if((a.x-lowx)*(b.y-lowy)==(b.x-lowx)*(a.y-lowy))
		return (a.x-lowx)*(a.x-lowx)+(a.y-lowy)*(a.y-lowy)<(b.x-lowx)*(b.x-lowx)+(b.y-lowy)*(b.y-lowy);
	return (a.x-lowx)*(b.y-lowy)-(b.x-lowx)*(a.y-lowy) > 0;
}

void output()
{
	for(int i = 0; i <= p; i++)
		printf("%d ",s[i]);
	printf("\n");
}

void GRAHAM_SCAN()
{
	int i;

	s[0] = 0;
	i = 1;
	while(i<n-1&&(Q[i].x-lowx)*(Q[i+1].y-lowy)==(Q[i+1].x-lowx)*(Q[i].y-lowy))
		i++;
	s[1] = i++;s[2] = i++;
	p = 2;
	while(i < n)
	{
		//output();		
		if(i<n-1&&(Q[i].x-lowx)*(Q[i+1].y-lowy)==(Q[i+1].x-lowx)*(Q[i].y-lowy))
		{
			i++;
			continue;
		}
		while((Q[s[p-1]].x-Q[s[p]].x)*(Q[i].y-Q[s[p]].y)>=(Q[i].x-Q[s[p]].x)*(Q[s[p-1]].y-Q[s[p]].y))
			p--;
		s[++p] = i;
		i++;
		//output();
		//system("pause");
	}
}

void input()
{
	int i;
	double ans = 0;
	//FILE *in, *out;

	//in = fopen("in.txt","r");
	//out = fopen("out.txt","w");
	fscanf(stdin,"%d%d",&n,&L);
	low = 0;
	for(i = 0; i < n; i++)
	{
		fscanf(stdin,"%d%d",&Q[i].x,&Q[i].y);
		if(i)
		{
			if(Q[i].y < Q[low].y||(Q[i].y == Q[low].y&&Q[i].x<Q[low].x))
				low = i;
		}
	}
	lowx = Q[low].x; lowy = Q[low].y;
	sort(Q,Q+n,cmp);
	GRAHAM_SCAN();
	//for(i = 0; i < n; i++)
	//	fprintf(out,"%d %d\n",Q[i].x,Q[i].y);
	for(i = 0; i <= p; i++)
	{
	//	fprintf(out,"%d ",s[i]);
		ans += sqrt((Q[s[i]].x-Q[s[(i+1)%(p+1)]].x)*(Q[s[i]].x-Q[s[(i+1)%(p+1)]].x)+(Q[s[i]].y-Q[s[(i+1)%(p+1)]].y)*(Q[s[i]].y-Q[s[(i+1)%(p+1)]].y));
	}
	ans += 2*PI*L;
	fprintf(stdout,"%.0lf\n",ans);
	//fclose(in);
	//fclose(out);
}

int main()
{
	input();
	return 1;
}