UVa11853 Paintball

题目大概意思是，在给定一个矩形内，给定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
#include 
#include 
#include
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){memset(vis, 0, sizeof(vis));memset(Enemy, 0, sizeof(Enemy));for(int i=0;i> Enemy[i].x >> Enemy[i].y >> Enemy[i].r;}bool isflag = false;for(int i=0;i=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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！