/**//* 好题! 题意:给出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
搜索
最新评论
|
|