题目大概意思是，在给定一个矩形内，给定n个圆（0n1000)是障碍物，让你找出一条路径从x=0到x=1000 。开始我想错了，后来看大佬的解释，才知道原来可以自上而下以圆来做DFS，意思就是先找和y=1000相切或相交的圆，然后再做DFS，搜索与它相交或相切的圆，如果圆和x=0相切或相交，可以利用y-r*r-x*x求出最上边那个点（画个图更容易理解）
同样x=1000也是这样求的。要注意的是必须要遍历完所有和y=1000相交或相切的点，因为之前如果没有到达最下面y=0，不代表下一个圆遍历不到y=0。遍历过的点不需要再遍历。
#include<iostream> #include <string.h> #include <algorithm> #include<math.h> using namespace std; int n; struct Node { double x, y, r; }; double wid = 1000.00; Node Enemy[1010]; int vis[1010]; double start = 1000.00, endans = 1000.00; bool dfs(int u) { vis[u] = 1; if (Enemy[u].y - Enemy[u].r <= 0.0)return true; if(Enemy[u].x<=Enemy[u].r) { start = min(Enemy[u].y-sqrt(Enemy[u].r*Enemy[u].r - Enemy[u].x*Enemy[u].x), start); } if(Enemy[u].x+Enemy[u].r>=wid) { endans = min(Enemy[u].y-sqrt(Enemy[u].r*Enemy[u].r - (wid-Enemy[u].x)*(wid-Enemy[u].x)), endans); } for(int i=0;i<n;i++) { if(!vis[i]&&(sqrt((Enemy[i].x-Enemy[u].x)*(Enemy[i].x-Enemy[u].x)+ (Enemy[i].y - Enemy[u].y)*(Enemy[i].y - Enemy[u].y))<=(Enemy[i].r+Enemy[u].r))) { if(dfs(i))return true; } } return false; } int main() { while(cin >> n) { memset(vis, 0, sizeof(vis)); memset(Enemy, 0, sizeof(Enemy)); for(int i=0;i<n;i++) { cin >> Enemy[i].x >> Enemy[i].y >> Enemy[i].r; } bool isflag = false; for(int i=0;i<n;i++) { if(Enemy[i].y+Enemy[i].r>=wid) { if(!vis[i]&&dfs(i)) { cout << "IMPOSSIBLE" << endl; isflag = true; break; } } } if(!isflag) printf("0.00 %.2lf 1000.00 %.2lf\n", start, endans); start = 1000.00; endans = 1000.00; } return 0; }
