定长圆覆盖最多点问题
问题描述,给出二维平面内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);
}
}
//欢迎围观,请大神轻拍~~~