比赛 20110728 评测结果 WATTTTTTTT
题目名称 打蚊子 最终得分 10
用户昵称 PurpleShadow 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 10:55:09
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2001;
const double eps=1e-8;
struct node
{
	double x,y;
	node(){}
	node(const double& _x,const double& _y):x(_x),y(_y){}
	bool operator<(const node &t)const
	{return x<t.x;}
};
int n,R;
node p[N];
void init()
{
	scanf("%d%d",&n,&R);
	for (int i=1;i<=n;++i)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1);
}
inline double sqr(const double &a)
{return a*a;}
inline double dis(const node &a,const node &b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
int Check(node a,node b)
{
	if (dis(a,b)-2*R>eps) return 0;
	node c((a.x+b.x)/2,(a.y+b.y)/2);
	double d=sqrt(sqr(R)-sqr(dis(a,c)));
	double t=sqrt(sqr(a.y-b.y)+sqr(a.x-b.x)),Sin=(a.y-b.y)/t,Cos=(a.x-b.x)/t;
	node o=node(c.x-d*Sin,c.y+d*Cos);
	int sum1=0;
	node* x=p+1;
	for (int i=1;i<=n;++i)
		if (R-dis(o,*x++)>-eps) ++sum1;
	o=node(c.x+d*Sin,c.y-d*Cos);
	int sum2=0;
	x=p+1;
	for (int i=1;i<=n;++i)
		if (R-dis(o,*x++)>-eps) ++sum2;
	return max(sum1,sum2);
}
void slove()
{
	int ans=0;
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n&&p[j].x-p[i].x-2*R<eps;++j)
			ans=max(ans,Check(p[i],p[j]));
	printf("%d\n",ans);
}
int main()
{
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
	init();
	slove();
	return 0;
}