http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1318
你是一个圆，二维坐标中有很多其他n个圆，给出n个圆心及半径，再给你自己的圆心及半径，问这个圆能不能逃出这n个圆的包围。
好神奇的题。。首先考虑把自己这个圆变成点，把别的圆的半径加上自己这个半径就好了。如果某两个圆相交或相切，那么他们组成的封闭区间可以用连接其两圆心的线段表示，这样能得到若干线段，于是问题变成，若干线段中，是否能组成一个封闭区域，且起始圆心在其内。 按顺时针扫描每一条边，如果点在里面，点与所有线段两个端点角度和为2π,如果逆时针来，就是-2π。 如果在多边形外的话，和必然是0，于是加边i j 边权为从起始圆心到I和到j的角度和（正负各加一条），如果整个图有负环，就相当于找到一个-2π，说明出不去了，spfa即可。。
#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <cmath> #include <algorithm> using namespace std; const int maxn = 340; const double eps = 1e-8; int n,tot,head[maxn],num[maxn]; bool inq[maxn]; struct Tcircle{ double x,y,r; }p[maxn]; double dis[maxn]; struct node{ int u,v,next; double w; }edges[maxn*maxn]; void add(int u,int v,double w){ edges[tot].v = v;edges[tot].w = w;edges[tot].next = head[u];head[u] = tot++; } void init(){ tot = 0;memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i = 1 ;i <= n ; i++){ scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r); } scanf("%lf%lf%lf",&p[0].x,&p[0].y,&p[0].r); for(int i = 1; i <= n ; i++) p[i].r += p[0].r; } double dist(int i,int j){ return sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) ); } bool spfa(){ queue<int>q; for(int i = 1;i <= n;i++){ q.push(i); inq[i] = true; num[i] = 0; dis[i] = 0.0; } while(!q.empty()){ int tmp = q.front();q.pop(); inq[tmp] = 0; for(int k = head[tmp];k != -1;k = edges[k].next){ if(dis[edges[k].v] > eps+dis[tmp]+edges[k].w){ dis[edges[k].v] = dis[tmp]+edges[k].w; if(!inq[edges[k].v]){ inq[edges[k].v] = true; q.push(edges[k].v); num[edges[k].v]++; if(num[edges[k].v] > n-1) return true; } } } } return false; } void sov(){ for(int i = 1; i <= n ; i++){ for(int j = i+1 ; j <= n ; j++){ if(p[i].r+p[j].r-dist(i,j) <= eps) continue; double ang = ( (p[i].x-p[0].x)*(p[j].x-p[0].x) + (p[i].y-p[0].y)*(p[j].y-p[0].y) )/dist(0,i)/dist(0,j); ang = acos(ang); if( (p[i].x-p[0].x) *(p[j].y-p[0].y) - (p[j].x-p[0].x) * (p[i].y-p[0].y) >= 0){ add(i,j,ang);add(j,i,-ang); } else{ add(i,j,-ang);add(j,i,ang); } } } } int main(){ int T; scanf("%d",&T); while(T--){ init(); sov(); if(spfa()) printf("NO\n"); else printf("YES\n"); if(T) printf("\n"); } }