题意 : 给你很多点和一个半径r,这个半径为r的圆能覆盖的最多的点是多少。
思路 : 对每个点做半径为 r 的圆, 求交集,交集最多的区域的被覆盖次数就是能覆盖的最多的点。贴两个链接,分析的挺好,代码写得挺好
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm> using namespace std ; const double eps = 1e- ;
const double PI = acos(-1.0) ;
int n ;
double r ; struct point
{
double x,y ;
}p[] ;
struct node
{
double angle ;
int flag ;
}q[] ; inline int dcmp(double d)
{
return d < -eps ? - : d > eps ;
}
bool cmp(const node &a,const node &b)//角度区间排序
{
if(dcmp(a.angle-b.angle) == ) return a.flag > b.flag ;
return a.angle < b.angle ;
}
double Sqrt(double x)
{
return x*x ;
}
double dist(const point &a,const point &b)
{
return sqrt(Sqrt(a.x-b.x)+Sqrt(a.y-b.y)) ;
} int main()
{
while(~scanf("%d %lf",&n,&r))
{
if(n == ) break ;
for(int i = ; i < n ; i++)
scanf("%lf %lf",&p[i].x,&p[i].y) ;
int ans = ;
for(int i = ; i < n ; i++)
{
int m = ;
for(int j = ; j < n ; j++)
{
if(i == j) continue ;
double d = dist(p[i],p[j]) ;
if(d > *r+0.001) continue ;
double s = atan2(p[j].y-p[i].y,p[j].x-p[i].x) ;
if(s < ) s += *PI ;//角度区间修正
double ph = acos(d/2.0/r) ;//圆心角转区间
q[m++].angle = s - ph + *PI ;q[m-].flag = ;
q[m++].angle = s + ph + *PI ;q[m-].flag = - ;
}
sort(q,q+m,cmp) ;
int sum = ;
for(int j = ; j < m ; j++)
ans = max(ans,sum += q[j].flag) ;
}
printf("It is possible to cover %d points.\n",ans+) ;
}
return ;
}