题目4 : 剑刃风暴
时间限制:20000ms
单点时限:2000ms
内存限制:256MB
描述
主宰尤涅若拥有一招非常厉害的招式——剑刃风暴，“无论是战士还是法师，都害怕尤涅若的武士刀剑技”。
现在战场上有N名敌对英雄，他们的位置分别为(Xi, Yi)，而剑刃风暴的伤害范围是一个半径为R的圆形，尤涅若可以选择一个坐标作为剑刃风暴的中心，所有处于这个圆形范围内的英雄都会受到剑刃风暴的伤害。
现在尤涅若想要知道，他的剑刃风暴最多可以同时伤害到多少敌对英雄。
输入
第一行为两个整数N和R，分别敌对英雄的数量以及剑刃风暴的半径。
接下来的N行，每行两个整数Xi和Yi，描述一个英雄的坐标。
对于30%的数据，满足1<=N<=10
对于60%的数据，满足1<=N<=100
对于100%的数据，满足1<=N<=2000, 0<=Xi, Yi<=108, 1<=R<=108，可能有两名英雄的坐标是相同的。
输出
输出一行Ans，表示尤涅若的剑刃风暴最多能够伤害到的英雄数量。
- 样例输入
10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7- 样例输出
3
/*
可以证明最优的圆上至少有两个点（否则可以在不影响最优的情况下挪到满足条件）
然后枚举其中一个点，用类似扫描线的方法统计，只不过这个区间变成了圆心到该点的方位角 时间复杂度是O(n2lgn)
*/
#include<cmath>
#include<cstdio>
#include<algorithm>
#define pf(x) ((x)*(x))
using namespace std;
typedef double real;
const int N=2e5+;int n,r,dr;
struct Point{real x,y;}p[N];
struct node{real angle;bool in;}arc[N];
real dist(const Point &a,const Point &b){
return sqrt(pf(a.x-b.x)+pf(a.y-b.y));
}
bool cmp(const node &a,const node &b){
return a.angle!=b.angle?a.angle<b.angle:a.in>b.in;
}
void MaxCirleCover(){
int ans=;
for(int i=;i<=n;i++){
int cnt=;real len=;
for(int j=;j<=n;j++){
if(i==j) continue;
if((len=dist(p[i],p[j]))>dr) continue;
real angle=atan2(p[i].y-p[j].y,p[i].x-p[j].x);
real phi=acos(len/dr);
arc[cnt].angle=angle-phi;arc[cnt++].in=true;
arc[cnt].angle=angle+phi;arc[cnt++].in=false;
}
sort(arc,arc+cnt,cmp);
int tmp=;
for(int i=;i<cnt;i++){
if(arc[i].in) tmp++;
else tmp--;
ans=max(ans,tmp);
}
}
printf("%d\n",ans);
}
int main(){
scanf("%d%d",&n,&r);dr=r*;
for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
MaxCirleCover();
return ;
}