UVa 11853 战场（paintball）

在一个尺寸为1000 * 1000的作战区域中，其西南角的坐标设定为(0,0)，而西北角的坐标则为(0,1000)。该区域中共存在n个敌方单位，其中第i个敌人的位置位于(xi,yi)，并具有ri的攻击半径。为了避免受到攻击，在任何时间点，你与每个敌人之间的距离必须严格大于或等于其攻击半径。你的目标是从战场西侧（x=0，y尽可能大）进入，并从东侧以类似的方式离开。

关键点如下：

• 采用从上至下的BFS方法进行检测，判断是否存在通往底部的路径。如果存在，则任务无法完成。
• 为何选择连接左右边界的圆的最南端交点作为进出点？这是因为遍历方向是从上至下进行的，一旦发现某个圆与左右边界存在交点，则表明该交点上方的空间已被封闭，无法通行。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e3 + 10;
    bool vis[maxn];
    
    struct Circle {
    double x, y, r;
    friend istream& operator >> (istream &in, Circle &c) {
        in >> c.x >> c.y >> c.r;
        return in;
    }