題目大意:
給你兩個數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;
}