题意：有n个敌人，每个敌人有一个攻击范围，问你是否存在从西边到东边的路径，如果存在，输出入点和出点最靠北的坐标。
把每个敌人看出一个圆，从上往下跑dfs连通，如果到达底部，那么无解。要求出最靠北的坐标，就在dfs过程中沿途检查与边界相交的点，并更新边界坐标。
#include<cstdio> #include<cstring> //#include<vector> //#include<queue> #include<algorithm> #include<math.h> //#define local using namespace std; const int maxn = 1000 + 1; const double W = 1000; int x[maxn], y[maxn], r[maxn]; int n; double left,right; bool intersect(int a,int b) { return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])) < r[a]+r[b]; } void check(int u) { if(x[u] < r[u]) left = min(left, y[u] - sqrt(r[u]*r[u] - x[u]*x[u])); if(x[u]+r[u] > W) right = min(right,y[u] - sqrt(r[u]*r[u] - (W-x[u])*(W-x[u]) ) ) ; } int vis[maxn]; //top to bottom bool dfs(int u) { if(vis[u]) return false; vis[u] = 1; if(y[u] < r[u]) return true; for(int v = 0; v < n; v++){ if(intersect(u,v) && dfs(v)) return true; } check(u); return false; } int main() { #ifdef local freopen("in.txt","r",stdin); #endif // local while(~scanf("%d",&n)) { bool ok = true; memset(vis,0,sizeof(vis)); left = right = W; for(int i = 0; i < n; i ++){ scanf("%d%d%d",x+i,y+i,r+i); } for(int i = 0; i < n; i ++) { if(r[i]+y[i]>=W && dfs(i)) {ok = false; break;} } if(ok) printf("0.00 %.2lf 1000.00 %.2lf ",left,right); else printf("IMPOSSIBLE "); } return 0; }