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