比赛 20110728 评测结果 AAWWAWWWWA
题目名称 打蚊子 最终得分 40
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 11:49:00
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=2002;
const int oo=1000000000;
const int tim=3000000;

int ux,uy,dx,dy,n,i,j,k,ans,tot,ci;
double x[MAXN],y[MAXN],r,cx,cy;


int main()
{
	freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
	scanf("%d%lf",&n,&r);
	ux=uy=-oo;
	dx=dy=oo;
	srand(1);
	for (i=1;i<=n;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
		if (x[i]>ux) ux=x[i];
		if (x[i]<dx) dx=x[i];
		if (y[i]>uy) uy=y[i];
		if (y[i]<dy) dy=y[i];
	}
	ci=tim/n;
	ans=0;
	while (ci--)
	{
		tot=0;
		cx=rand()%(ux-dx+1)+dx;
		cy=rand()%(uy-dy+1)+dy;
		for (i=1;i<=n;i++)
			if (sqrt((cx-x[i])*(cx-x[i])+(cy-y[i])*(cy-y[i]))<=r) ++tot;
		if (tot>ans) ans=tot;
	}
	printf("%d\n",ans);
	return 0;
}