注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

判断N个圆是否有公共部分  

2011-04-16 21:25:37|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目来自Poj Challenge
这题的算法:二分相交部分的横坐标。
用一条直线x=x0和所有圆计算交点,如果有的圆不和它相交,易知交集和直线的左右关系。
如果所有圆和直线的相交的部分的交集非空,那么输出yes。
如果某两个圆和直线的相交部分不相交,那么这两个圆的交点肯定在直线的同侧,由此可得左右关系。
这样就可以了。

我想出了另外一个算法,复杂度未知,正确性没试,如果有人能给一个分析或者写出来交上去,恳请留言。
把圆random_shuffle。
从第一个圆开始。随便选个点。
依次考察后面的每个圆,如果当前的点在圆内部,就继续,否则,
计算这个圆和它前面的圆的交点,尝试找到一个在所有圆中的点。可以知道如果总的交集非空,那么在这个圆上一定有交集(因为这个圆的加入改变了总交集)。
从情感角度讲,当前交集越小,当前点在圆内部的概率就越大,所以总的时间复杂度应该是Ω(NlogN)。不过我还没有验证。

附:二分法的代码
#include <cstdio>
#include <algorithm>
#include <math.h>
#define NMax 100000
using namespace std;
struct v2{
double x,y;
v2(){}
v2(double _x,double _y):x(_x),y(_y){}
};
v2 A[NMax];
double R[NMax];
int N;
int getCross(const v2 &a,double r1,const v2 &b,double r2,v2 &r,v2 &rr){
double l2=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
if (l2>(r1+r1)*(r2+r2))return 0;
double l=sqrt(l2);
double cs0=(b.x-a.x)/l,sn0=(b.y-a.y)/l;
double cs1=(r1*r1+l2-r2*r2)*0.5/r1/l,sn1=sqrt(1.0-cs1*cs1);
r=v2(a.x+r1*(cs0*cs1-sn0*sn1),a.y+r1*(cs0*sn1+cs1*sn0));
rr=v2(a.x+r1*(cs0*cs1+sn0*sn1),a.y+r1*(-cs0*sn1+cs1*sn0));
return 1;
}
int main()
{
scanf("%d",&N);
double left,right;
for (int i=0;i<N;i++){
int x,y,r;
scanf("%d%d%d",&x,&y,&r);
A[i]=v2(x,y);
R[i]=r;
if (!i)left=x-r,right=x+r;
else left=max(left,(double)(x-r)),right=min(right,double(x+r));
}
if (left>=right){
puts("NO");
return 0;
}
int z=20;
while (z--){
double mid=0.5*(right+left);
int a,b;
double h,l;
for (int i=0;i<N;i++){
double d=sqrt(R[i]*R[i]-(mid-A[i].x)*(mid-A[i].x));
double u=A[i].y-d,v=A[i].y+d;
if (i==0 || u>l)l=u,a=i;
if (i==0 || v<h)h=v,b=i;
}
if (h>l){
puts("YES");
return 0;
}
v2 k,p;
if (!getCross(A[a],R[a],A[b],R[b],k,p)){
puts("NO");
return 0;
}
if (0.5*(k.x+p.x)<mid)right=mid;
else left=mid;
}
puts("NO");
return 0;
}

  评论这张
 
阅读(1514)| 评论(10)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017