比赛 |
20110728 |
评测结果 |
AAAAAAAAAA |
题目名称 |
打蚊子 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-28 11:36:08 |
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<double,int> Pair;
typedef long long Int;
const int MAXN=2005;
const double eps=1e-6;
const double PI=acos(-1);
#define pb push_back
#define mp make_pair
struct Point
{
int x,y;
}P[MAXN];
Int sqr(Int x)
{
return x*x;
}
Int dis2(const Point &a,const Point &b)
{
return sqr(a.x-b.x)+sqr(a.y-b.y);
}
int N,R;
vector<Pair> v;
int main()
{
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
scanf("%d%d",&N,&R);
for(int i=0;i<N;i++)
scanf("%d%d",&P[i].x,&P[i].y);
int re=0;
random_shuffle(P,P+N);
for(int i=0;i<N;i++)
{
v.clear();
double t;
int x=0;
for(int j=0;j<N;j++)
if (i!=j && (t=dis2(P[i],P[j]))<=4LL*R*R+eps)
{
double alpha=atan2(P[j].y-P[i].y,P[j].x-P[i].x);
double beta=acos(sqrt(t)/(2.0*R));
if (alpha<0)
alpha+=2*PI;
v.pb(mp(alpha-beta+2*PI,0));
v.pb(mp(alpha+beta+2*PI,1));
x++;
}
if (x<=re)
continue;
sort(v.begin(),v.end());
int sum=0;
for(vector<Pair>::iterator it=v.begin();it!=v.end();it++)
if (it->second)
sum--;
else
{
sum++;
if (sum>re)
re=sum;
}
}
printf("%d\n",re+1);
return 0;
}