比赛 |
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;
}