UVa 11853 Paintball

题目描述你正在一个1000×10001000 \times 10001000×1000的正方形场地上玩彩弹游戏。场地上有若干对手躲在树后每个对手位于(x,y)(x, y)(x,y)位置并且可以朝任意方向发射彩弹攻击范围为rrr。如果你在移动过程中进入任何对手的攻击范围就会被击中。场地左下角为(0,0)(0,0)(0,0)左上角为(0,1000)(0,1000)(0,1000)。你必须从场地的左侧边介于西南角和西北角之间进入从右侧边介于东南角和东北角之间离开。对于每个场景判断是否能完成穿越。如果能输出进入点和离开点的坐标保留两位小数且要选择最北的入口如果不能输出IMPOSSIBLE。输入格式输入包含多个场景。每个场景的第一行是整数n≤1000n \leq 1000n≤1000表示对手数量。接下来nnn行每行包含三个实数对手的(x,y)(x, y)(x,y)坐标和攻击半径rrr。输出格式对于每个场景输出四个实数保留两位小数表示进入和离开坐标或者输出IMPOSSIBLE。样例输入3 500 500 499 0 0 999 1000 1000 200样例输出0.00 1000.00 1000.00 800.00题目分析问题本质这是一个平面几何连通性问题每个对手相当于一个圆形禁区圆心(x,y)(x, y)(x,y)半径rrr我们需要判断是否存在一条从左边界到右边界的路径全程不进入任何圆形禁区如果存在还要找到最北的入口和出口关键观察屏障效应如果存在一组相连的圆形成从上边界到下边界的连续屏障则无法穿越边界阻挡即使没有完整屏障某些圆可能阻挡左侧或右侧的特定区域影响入口和出口的选择解题思路第一步判断可行性是否存在通路使用并查集Union-Find\texttt{Union-Find}Union-Find来判断是否存在从上边界到下边界的连续屏障合并相交的圆如果两个圆的圆心距离小于等于半径之和它们相交属于同一连通分量标记边界接触如果一个圆与上边界y1000y 1000y1000相交或相切标记该连通分量接触上边界如果一个圆与下边界y0y 0y0相交或相切标记该连通分量接触下边界检查屏障如果存在某个连通分量同时接触上边界和下边界则形成完整屏障输出IMPOSSIBLE第二步寻找最北入口和出口使用BFS\texttt{BFS}BFS广度优先搜索从接触上边界的圆开始扩展阻挡区域初始化将所有接触上边界的圆加入队列BFS\texttt{BFS}BFS扩展不断将与当前圆相交的未访问圆加入队列更新边界阻挡对于每个访问到的圆检查是否与左边界x0x 0x0相交如果相交计算交点范围[y−r2−x2,yr2−x2][y - \sqrt{r^2 - x^2}, y \sqrt{r^2 - x^2}][y−r2−x2​,yr2−x2​]更新左边界阻挡的最南端为这些交点范围的最小值同样检查是否与右边界x1000x 1000x1000相交如果相交计算交点范围[y−r2−(1000−x)2,yr2−(1000−x)2][y - \sqrt{r^2 - (1000-x)^2}, y \sqrt{r^2 - (1000-x)^2}][y−r2−(1000−x)2​,yr2−(1000−x)2​]更新右边界阻挡的最南端为这些交点范围的最小值确定入口和出口最北入口 左边界阻挡的最南端如果无阻挡则为1000.001000.001000.00最北出口 右边界阻挡的最南端如果无阻挡则为1000.001000.001000.00算法正确性证明可行性判断如果存在连通分量同时接触上下边界则这些圆形成连续屏障无法穿越否则至少存在一条通路可以穿越场地最北入口确定所有接触上边界的圆及其相连圆构成顶部阻挡区域这个区域在左边界上的最南端点就是最北的安全入口因为任何比这个点更北的入口都会被顶部阻挡区域拦截参考代码// Paintball// UVa ID: 11853// Verdict: Accepted// Submission Date: 2025-10-30// UVa Run Time: 0.010s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleeps1e-8;constdoubleW1000.0;structCircle{doublex,y,r;};doubledist(doublex1,doubley1,doublex2,doubley2){returnhypot(x1-x2,y1-y2);}boolcirclesIntersect(constCirclea,constCircleb){returndist(a.x,a.y,b.x,b.y)a.rb.reps;}intparent[1005];intfind(intx){if(parent[x]!x)parent[x]find(parent[x]);returnparent[x];}voidunite(inta,intb){afind(a);bfind(b);if(a!b)parent[a]b;}intmain(){ios_base::sync_with_stdio(false);cin.tie(NULL);intn;while(cinn){vectorCircleenemies(n);for(inti0;in;i){cinenemies[i].xenemies[i].yenemies[i].r;}// 第一步用并查集判断是否存在通路 for(inti0;in;i)parent[i]i;// 合并相交的圆for(inti0;in;i){for(intji1;jn;j){if(circlesIntersect(enemies[i],enemies[j])){unite(i,j);}}}// 检查每个连通分量是否同时接触上边界和下边界vectorbooltop(n,false),bottom(n,false);for(inti0;in;i){introotfind(i);if(enemies[i].yenemies[i].rW-eps)top[root]true;if(enemies[i].y-enemies[i].reps)bottom[root]true;}boolimpossiblefalse;for(inti0;in;i){if(parent[i]itop[i]bottom[i]){impossibletrue;break;}}if(impossible){coutIMPOSSIBLE\n;continue;}// 第二步寻找最北入口和出口 vectorboolvisited(n,false);doubleleftBlockW;// 左边界阻挡的最南端初始为最北doublerightBlockW;// 右边界阻挡的最南端初始为最北// BFS 从接触上边界的圆开始扩展阻挡区域vectorintqueue;for(inti0;in;i){if(enemies[i].yenemies[i].rW-eps){// 接触上边界visited[i]true;queue.push_back(i);}}// BFS 扩展阻挡区域for(intidx0;idxqueue.size();idx){intuqueue[idx];constCirclecenemies[u];// 更新左边界阻挡if(c.x-c.reps){// 接触左边界doubledysqrt(max(0.0,c.r*c.r-c.x*c.x));// 避免数值误差doublebottomYc.y-dy;if(bottomYleftBlock){leftBlockbottomY;}}// 更新右边界阻挡if(c.xc.rW-eps){// 接触右边界doubledxW-c.x;doubledysqrt(max(0.0,c.r*c.r-dx*dx));// 避免数值误差doublebottomYc.y-dy;if(bottomYrightBlock){rightBlockbottomY;}}// 扩展相邻圆for(intv0;vn;v){if(!visited[v]circlesIntersect(c,enemies[v])){visited[v]true;queue.push_back(v);}}}// 确定入口和出口坐标doubleenterY,exitY;if(leftBlockW-eps){// 没有圆阻挡左边界入口可以是 (0, 1000)enterYW;}else{// 阻挡区域最南端就是最北入口enterYleftBlock;// 如果阻挡区域延伸到 y 0 以下入口只能是0if(enterY0)enterY0;}if(rightBlockW-eps){// 没有圆阻挡右边界出口可以是 (1000, 1000)exitYW;}else{// 阻挡区域最南端就是最北出口exitYrightBlock;// 如果阻挡区域延伸到 y 0 以下出口只能是 0if(exitY0)exitY0;}// 输出结果coutfixedsetprecision(2)0.00 enterY W exitY\n;}return0;}