题意：给出一个1000*1000大小的矩阵，里面有若干圆，表示障碍物，现在要找出从左边到右边的一条通路，输出入口和出口的坐标，如果有多答案，输出y值最大的答案。
分析：从与上面相连的圆开始dfs，每次找与之相交的圆作为dfs的路径，如果能访问到下面，那么左边和右边肯定是不连通的；否则，连通。并且在dfs的时候更新y值最大的答案。
具体见代码：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
#include <math.h>
using namespace std;
const int N = + ;
const int inf = 2e9;
typedef long long ll;
typedef pair<int,int> pii; int n;
int vis[N];
struct circle
{
int x,y,r;
void read()
{
scanf("%d%d%d",&x,&y,&r);
}
}c[N]; bool can(circle a,circle b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
double d = sqrt(dx*dx+dy*dy);
return d <= a.r + b.r;
} double ansL = , ansR = ;
void update(int u)
{
if(c[u].x <= c[u].r)
{
double t = sqrt(c[u].r*c[u].r - c[u].x*c[u].x);
double pos = c[u].y - t;
ansL = min(ansL, pos);
}
if(c[u].x + c[u].r >= )
{
double tt = 1000.0 - c[u].x;
double t = sqrt(c[u].r*c[u].r - tt*tt);
double pos = c[u].y - t;
ansR = min(ansR, pos);
}
} bool dfs(int u)
{
vis[u] = ;
if(c[u].y <= c[u].r) return false;
update(u);
for(int i=;i<=n;i++)
{
if(!vis[i] && can(c[u], c[i]))
{
if(!dfs(i)) return false;
}
}
return true;
} void solve()
{
ansL = , ansR = ;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
if(!vis[i] && c[i].y + c[i].r >= )
{
if(!dfs(i))
{
puts("IMPOSSIBLE");
return ;
}
}
}
printf("0.00 %.2f 1000.00 %.2f\n",ansL,ansR);
} int main()
{
while(scanf("%d",&n) == )
{
for(int i=;i<=n;i++) c[i].read();
solve();
}
return ;
}