定长圆覆盖最多点问题
问题描述，给出二维平面内N个点的(x,y)坐标，给一固定半径R。求一圆，圆心位置任意，要求尽可能多的覆盖平面点集中的点。输出最多的覆盖点数。
（限制条件，保证无任意两点距离等于2R，即无两点连线恰为直径。亦无任意三点同时在一个半径为R的圆上。）
朴素算法：由限制条件可知，最后目标圆圆心一定可由某两点唯一确定（即目标圆的圆弧上一定恰有两个平面点集中的点）。具体实现：C(N,2)枚举任意两圆，构造可行圆，枚举N个点，判断是否在圆上或者圆内（即是否被覆盖）。复杂度O(N^3)。
（如果过了就算是水过去的吧，没过就怪常数太大。。= =||）
我所知的标准做法：O(n^2*logn)的圆上交点扫描法。
转化为圆上的弧最多被覆盖几次的问题。
直觉可解，圆上某个弧如果被某个圆覆盖过，那么我们把目标圆圆心放在该段弧上时，目标圆一定能把该弧所在圆圆心覆盖（即平面点集中的某点）。
所以，被覆盖次数最多的弧的被覆盖次数即为目标圆（最优）最多能够覆盖的点数。
具体做法：
依旧是C(N,2)枚举任意两点，以BA为例，此时i=1,j=0。
求取BA的极角theta，利用atan2（因变量范围(-pi,pi]）。
为方便极角排序，对于负角要+2pi。
B、A构造的圆交于X1，X4两点，求取X1B与BA的夹角和X4B与AB的夹角（相同）。
Phi ，acos(D/2.0/R)，D=dis(A,B)。
以上可得出两圆交点在当前圆上对于圆心的极角。
为方便极角排序，每个极角均加2pi，使域扩张到[0，4pi]，从而防止了跨0角的出现。
alpha[t].value=theta – phi + 2pi,alpha[t].flag = 1(弧的进入端)
alpha[t+1].value = theta + phi + 2pi,alpha[t+1].flag = false（弧的退出端）。
接下来，对于每个圆上的t（偶数）个极角进行排序，再顺序扫描，动态更新最大值。
for(i,0,t)
if(alpha[i].flag)
sum++
else
sum--
if(sum > ans)
ans = sum
最后输出答案时，输出ans+1即可。（因为要算上弧所在圆自身）
复杂度：O(n *(nlogn + t))=O(n^2*logn)
题目链接：
http://poj.org/problem?id=1981http://boj.me/onlinejudge/showproblem.php?problem_id=1679#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Mn 300//平面点集中点数
using namespace std;
const double eps = 1e-9;//精度调高点没跑~
const double pi = acos(-1.0);
#define sqr(x) ((x) * (x))
double R;//定长
struct point
{
double x,y;
void read()
{
scanf("%lf%lf",&x,&y);
}
void print()
{
printf("%lf%lf\n",x,y);
}
double friend dis(const point &a,const point &b)
{
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
}p[Mn + 5];
struct alpha
{
double v;
bool flag;
bool friend operator <(const alpha &a,const alpha &b)//排序专用偏序关系
{
return a.v < b.v;
}
}alp[Mn * Mn + 5];//C(N,2)*2的可能交点（可能极角）
void solve(int n)
{
R = 1.0;//本题内为单位圆
for(int i = 0;i < n;i++)
p[i].read();
int MAX = 0;
for(int i = 0;i < n;i++)
{
int t = 0;
for(int j = 0;j < n;j++)
{
if(i == j)
continue;
double theta,phi,D;
D = dis(p[i],p[j]);
if(D > 2.0 * R)//距离超界直接秒杀
continue;
//关键部分
theta = atan2(p[j].y - p[i].y,p[j].x - p[i].x);
if(theta < 0)
theta += 2 * pi;
phi = acos(D / (2.0 * R));
alp[t].v = theta - phi + 2 * pi;
alp[t].flag = true;
alp[t + 1].v = theta + phi + 2 * pi;
alp[t + 1].flag = false;
t += 2;
}
sort(alp,alp + t);
int sum = 0;
for(int j = 0;j < t;j++)
{
if(alp[j].flag)
sum ++;
else
sum --;
if(sum > MAX)
MAX = sum;
}
}
printf("%d\n",MAX + 1);
}
int main()
{
int n;
while(scanf("%d",&n) == 1 && n)
{
solve(n);
}
}
//欢迎围观，请大神轻拍~~~