1981.txt

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

#include"iostream.h"
#include"math.h"
#include"algorithm"

struct point
{
	double x,y;
}p[310];

double jl(point i,point j)
{
	return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}



bool fzk(point a,point b,double &in,double &out)
{
	double jiao,l,x;
	if((l=jl(a,b))>2)return 0;

	jiao=atan2(b.y-a.y,b.x-a.x);

	x=acos(l/2);

	in=jiao-x;
	out=jiao+x;
	
	return 1;
}

int n,m;
struct node
{
	char sign;
	double jiao;
}t[310];

int cmp(node a,node b)
{
	return a.jiao<b.jiao;
}


void doit()
{
	int i,j,answer,now,kh;
	double a,b;
		
	answer=1;

	for(i=0;i<n;i++)
	{
		m=0;
		for(j=0;j<n;j++)
		{
			if(i!=j&&fzk(p[i],p[j],a,b))
			{
				t[m].jiao=a;t[m].sign=1;m++;
				t[m].jiao=b;t[m].sign=2;m++;
			}
		}

		std::sort(&t[0],&t[m],cmp);

		now=1;kh=9999;
	//	for(j=0;j<m&&t[j].sign==2;j++)
	//		;
		if(m)
		for(j=0;j<m+kh;j++)
		{
			if(kh==9999&&t[j%m].sign==2)kh=j+1;
			if(t[j%m].sign==1)now++;
			else now--;
			if(now==0)while(1)
				cout<<"error";

			if(now>answer)answer=now;
		}

	}

	cout<<answer<<endl;
}

int main()
{
	int i;
	while(1)
	{
		cin>>n;
		if(n==0)break;
		for(i=0;i<n;i++)
			cin>>p[i].x>>p[i].y;

		doit();
	}

	return 0;
}