题目大意:
给你两个数n,r
再给你n个坐标
然后问你一个半径为r的圆最多能包括多少坐标
思路:
当有多个点在圆里的时候
可以通过移动圆让两点在圆上并且其他点依然在圆里面
(感觉就相当于把所有点往一个方向平移直到离这个方向边界最近的两个点在圆上为止
这个时候肯定其他点依旧在圆内)
然后就枚举两点
找到圆心之后再枚举多少个点在圆里找最大就好了
AC代码:
#include <bits/stdc++.h>
#define pf(x) (x)*(x)
using namespace std;
struct node{
double x,y;
}a[110];
double r;
double eps=1e-6;
double calc_dist(node b,node c){
return sqrt(pf(b.x-c.x)+pf(b.y-c.y));
}
node calc(node b,node c){
node d;
d.x=(b.x+c.x)/2.0;
d.y=(b.y+c.y)/2.0;
double dis=calc_dist(d,b);
double h=sqrt(pf(r)-pf(dis));
double p=-1*atan2(b.x-c.x,b.y-c.y);
d.x+=h*cos(p);
d.y+=h*sin(p);
return d;
}
int main()
{
int n;
cin>>r>>n;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
int ans=1;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
node c=calc(a[i],a[j]);
int num=0;
// cout<<c.x<<' '<<c.y<<endl;
for(int k=0;k<n;k++){
if(calc_dist(c,a[k])<r+eps)num++;
}
ans=max(ans,num);
}
}
cout<<ans;
return 0;
}