POJ 1981 Circle and Points 【定长圆覆盖最多点问题】

定长圆覆盖最多点问题

问题描述,给出二维平面内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

BA构造的圆交于X1X4两点,求取X1BBA的夹角和X4BAB的夹角(相同)。

Phi acos(D/2.0/R)D=dis(A,B)

以上可得出两圆交点在当前圆上对于圆心的极角。

为方便极角排序,每个极角均加2pi,使域扩张到[04pi],从而防止了跨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=1981
http://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);

    }

}

//欢迎围观,请大神轻拍~~~

posted on 2011-07-05 13:14 BUPT-[aswmtjdsj] @ Penalty 阅读(3606) 评论(0)  编辑 收藏 引用 所属分类: 计算几何BOJ Solution ReportPOJ Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜