 /**//*
好題!
題意:給出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
搜索
最新評論

|
|