比赛 20110728 评测结果 AAAAAAAAAA
题目名称 打蚊子 最终得分 100
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 11:36:08
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<double,int> Pair;
typedef long long Int;
const int MAXN=2005;
const double eps=1e-6;
const double PI=acos(-1);
#define pb push_back
#define mp make_pair

struct Point
{
	int x,y;
}P[MAXN];

Int sqr(Int x)
{
	return x*x;
}

Int dis2(const Point &a,const Point &b)
{
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}

int N,R;
vector<Pair> v;
int main()
{
	freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
	scanf("%d%d",&N,&R);
	for(int i=0;i<N;i++)
		scanf("%d%d",&P[i].x,&P[i].y);
	int re=0;
	random_shuffle(P,P+N);
	for(int i=0;i<N;i++)
	{
		v.clear();
		double t;
		int x=0;
		for(int j=0;j<N;j++)
			if (i!=j && (t=dis2(P[i],P[j]))<=4LL*R*R+eps)
			{
				double alpha=atan2(P[j].y-P[i].y,P[j].x-P[i].x);
				double beta=acos(sqrt(t)/(2.0*R));
				if (alpha<0)
					alpha+=2*PI;
				v.pb(mp(alpha-beta+2*PI,0));
				v.pb(mp(alpha+beta+2*PI,1));
				x++;
			}
		if (x<=re)
			continue;
		sort(v.begin(),v.end());
		int sum=0;
		for(vector<Pair>::iterator it=v.begin();it!=v.end();it++)
			if (it->second)
				sum--;
			else
			{
				sum++;
				if (sum>re)
					re=sum;
			}
	}
	printf("%d\n",re+1);
	return 0;
}