 /**//*
好题!
题意:给出n个圆心及半径,再给出一个特殊圆心几半径,问这个圆能不能逃出这n个圆的包围

首先先处理一下,将所有圆平移,使特殊圆在原点上,然后其他圆半径加上特殊圆的半径,这样特殊圆就可看成
一个点而已,问题变为该点是否可以逃出
实际上对于相交的两个圆,我们可以用他们圆心连线来代替它们。这样问题变为是否存在一个多边形,使得原点
在这个多边行内部。
判断点在多边形内一个比较简单有效的方法是按顺序扫描边,如果整个过程的有向视角之和为0的话,
点在多边形外,为2PI或-2PI的话,点在多边形内。
于是我们可以对所有相交的两个圆之间连两条有向边, 边权是对应的有向角。
答案取决于这个有向图里中是否存在负环
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;

const int MAXN=310;
const double DINF=1000000000.0;
const double eps=1e-6;

 struct Node {
int v,next;
double w;
}nodes[MAXN*MAXN];
int n;
double x[MAXN],y[MAXN],r[MAXN];
int G[MAXN];
bool vi[MAXN];
int in[MAXN];
double d[MAXN];
int alloc;

void add(int a,int b,double c)
  {
nodes[alloc].v=b,nodes[alloc].next=G[a];nodes[alloc].w=c;
G[a]=alloc++;
}
double dist(int a,int b)
  {
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
bool spfa()
  {
queue<int>Q;
 for(int i=1;i<=n;i++) {
Q.push(i);
vi[i]=1;
in[i]=0;
d[i]=0;//刚开始可视角和为0,因为就只有这个点,以后通过其他点去更新得到更小的
}
 while(!Q.empty()) {
int u=Q.front();Q.pop();
vi[u]=0;
 for(int son=G[u];son!=-1;son=nodes[son].next) {
int v=nodes[son].v;
double w=nodes[son].w;
 if(d[v]>eps+d[u]+w) {//卡精度!以后还是加个eps吧
d[v]=d[u]+w;
 if(!vi[v]) {
in[v]++;
if(in[v]>=n)return false;
vi[v]=1;
Q.push(v);
}
}
}
}
return true;
}
int main()
  {
//freopen("in","r",stdin);
int T;
scanf("%d",&T);
 while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
scanf("%lf%lf%lf",&x[0],&y[0],&r[0]);
 for(int i=1;i<=n;i++) {
x[i]-=x[0];
y[i]-=y[0];
r[i]+=r[0];
}
x[0]=y[0]=0;
//build
memset(G,-1,sizeof(G));
alloc=0;
for(int i=1;i<=n;i++)
 for(int j=i+1;j<=n;j++) {
if(r[i]+r[j]-eps<dist(i,j))continue;//<= 即擦着边也过不了
double C=acos( (x[i]*x[j]+y[i]*y[j])/(dist(i,0)*dist(j,0)) );
bool flag=(x[i]*y[j]-x[j]*y[i])>=0;//i在j的右边
add(i,j,flag?C:-C);
add(j,i,!flag?C:-C);
}
//有负环表示围成了一个多边形了!
printf(spfa()?"YES\n":"NO\n");
if(T)puts("");
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|