 /**//*
好題!
題意:給出n個(gè)圓心及半徑,再給出一個(gè)特殊圓心幾半徑,問(wèn)這個(gè)圓能不能逃出這n個(gè)圓的包圍

首先先處理一下,將所有圓平移,使特殊圓在原點(diǎn)上,然后其他圓半徑加上特殊圓的半徑,這樣特殊圓就可看成
一個(gè)點(diǎn)而已,問(wèn)題變?yōu)樵擖c(diǎn)是否可以逃出
實(shí)際上對(duì)于相交的兩個(gè)圓,我們可以用他們圓心連線來(lái)代替它們。這樣問(wèn)題變?yōu)槭欠翊嬖谝粋€(gè)多邊形,使得原點(diǎn)
在這個(gè)多邊行內(nèi)部。
判斷點(diǎn)在多邊形內(nèi)一個(gè)比較簡(jiǎn)單有效的方法是按順序掃描邊,如果整個(gè)過(guò)程的有向視角之和為0的話,
點(diǎn)在多邊形外,為2PI或-2PI的話,點(diǎn)在多邊形內(nèi)。
于是我們可以對(duì)所有相交的兩個(gè)圓之間連兩條有向邊, 邊權(quán)是對(duì)應(yīng)的有向角。
答案取決于這個(gè)有向圖里中是否存在負(fù)環(huán)
*/
#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;//剛開(kāi)始可視角和為0,因?yàn)榫椭挥羞@個(gè)點(diǎn),以后通過(guò)其他點(diǎn)去更新得到更小的
}
 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) {//卡精度!以后還是加個(gè)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;//<= 即擦著邊也過(guò)不了
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);
}
//有負(fù)環(huán)表示圍成了一個(gè)多邊形了!
printf(spfa()?"YES\n":"NO\n");
if(T)puts("");
}
return 0;
}
|
|
常用鏈接
隨筆分類
Links
搜索
最新評(píng)論

|
|