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

using namespace std;

const double eps=1e-2;
struct point
{
	double x,y;
}P[2001],M;
double R;
int n;
void init()
{
	scanf("%d%lf",&n,&R);
	for (int i=1;i<=n;i++)
	scanf("%lf%lf",&P[i].x,&P[i].y);
}

double dis(point &a,point &b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void calM(point &a,point &b)
{
	double d1=dis(a,b)/2;
	double d2=sqrt(R*R-d1*d1);
	M.x=(a.x+b.x)/2;M.y=(a.x+b.x)/2;
	if (abs(b.x-a.x)<eps)
	{
		M.y+=d2;
	}
	else if (abs(b.y-a.y)<eps)
	{
		M.x+=d2;
	}
	else
	{
		double k=(a.y-b.y)*(a.y-b.y)/(a.x-b.x)/(a.x-b.x);
		double deltax=d2*d2/(1+k);
		double deltay=d2*d2-deltax*deltax;
		M.x+=deltax * ( (a.y-b.y)/(a.x-b.x) >0 ? 1 : -1);
		M.y+=deltay;
	}
}

void calM2(point &a,point &b)
{
	double d1=dis(a,b)/2;
	double d2=sqrt(R*R-d1*d1);
	M.x=(a.x+b.x)/2;M.y=(a.x+b.x)/2;
	if (abs(b.x-a.x)<eps)
	{
		M.y-=d2;
	}
	else if (abs(b.y-a.y)<eps)
	{
		M.x-=d2;
	}
	else
	{
		double k=(a.y-b.y)*(a.y-b.y)/(a.x-b.x)/(a.x-b.x);
		double deltax=d2*d2/(1+k);
		double deltay=d2*d2-deltax*deltax;
		M.x-=deltax * ( (a.y-b.y)/(a.x-b.x) >0 ? 1 : -1);
		M.y-=deltay;
	}
}

void solve()
{
	int cnt=0,ans=0;
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
	if (dis(P[i],P[j])<=2*R+eps)
	{
		calM(P[i],P[j]);
		cnt=0;
		for (int k=1;k<=n;k++)
		{
			if (dis(P[k],M)<=R+eps)
			cnt++;
		}
		ans=max(ans,cnt);
		calM2(P[i],P[j]);	
		cnt=0;
		for (int k=1;k<=n;k++)
		{
			if (dis(P[k],M)<=R+eps)
			cnt++;
		}
		ans=max(ans,cnt);
	}
	printf("%d\n",ans);
}

int main()
{
	freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
	init();
	solve();
	return 0;
}