题解：英雄救公主的最远距离

算法思路

本题要求找到一条从 $(1,1)$ 到 $(row,line)$ 的路径，使得路径上距离 Boss 的最短距离最大化。这是一个典型的最大化最小值问题，采用二分答案 + BFS 判断的方法。

1. 问题转化

将问题转化为：判断是否存在一条路径，使得路径上每个点距离所有 Boss 都至少为 $d$。

2. 关键观察

• 如果英雄要与 Boss 保持距离 $d$，那么每个 Boss 周围半径为 $d$ 的区域都是"禁区"
• 这些禁区会形成连通块，可能阻断从起点区域到终点区域的路径

3. 算法步骤

1. 二分答案：在 $[0, \sqrt{(row-1)^2 + (line-1)^2}]$ 范围内二分最大距离 $d$
2. BFS 判断可行性：
   • 将 Boss 视为节点，如果两个 Boss 距离 $\leq 2d$，则它们所在的禁区连通
   • 检查是否存在禁区连通块同时连接了左/下边界和右/上边界
   • 如果存在这样的连通块，说明路径被阻断，$d$ 不可行

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
const double eps = 1e-3;
int n, row, line, x[N], y[N];
double t;
bool vis[N];
queue<int> q;

// BFS判断当前距离t是否可行
bool bfs() {
    memset(vis, 0, sizeof vis);
    
    // 从连接左边界或下边界的Boss开始
    for (int i = 1; i <= n; ++i)
        if (x[i] - 1 <= t || line - y[i] <= t)
            q.push(i), vis[i] = 1;
    
    // BFS扩展连通块
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 1; i <= n; ++i)
            if (!vis[i] && hypot(x[i] - x[u], y[i] - y[u]) <= 2 * t)
                q.push(i), vis[i] = 1;
    }
    
    // 检查是否有连通块同时连接右边界或上边界
    for (int i = 1; i <= n; ++i)
        if ((row - x[i] <= t || y[i] - 1 <= t) && vis[i])
            return true;
    
    return false;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> row >> line;
    
    for (int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    
    // 二分最大距离
    double l = 0, r = hypot(row - 1, line - 1);
    
    while (r - l > eps) {
        t = (l + r) / 2;
        
        if (bfs())
            r = t;  // 距离太大，路径被阻断
        else
            l = t;  // 距离可行，尝试更大的距离
    }
    
    printf("%.2lf", t);
    return 0;
}

关键点分析

1. 二分答案框架

• 搜索区间：$[0, \text{起点到终点的直线距离}]$
• 精度控制：$eps = 10^{-3}$，保证输出精确到小数点后两位

2. BFS 连通性判断

• 节点：每个 Boss 作为一个节点
• 边：如果两个 Boss 距离 $\leq 2d$，则它们所在的禁区连通
• 起点：连接左边界 $(x \leq 1+d)$ 或下边界 $(y \geq line-d)$ 的 Boss
• 终点：连接右边界 $(x \geq row-d)$ 或上边界 $(y \leq 1+d)$ 的 Boss

3. 几何解释

• 每个 Boss 的禁区是半径为 $d$ 的圆
• 两个 Boss 距离 $\leq 2d$ 时，它们的禁区相连形成更大的禁区
• 如果存在从左下边界到右上边界的禁区连通块，则路径被完全阻断

复杂度分析

• 时间复杂度：$O(n^2 \log(\frac{D}{\epsilon}))$
  • 二分：$O(\log(\frac{D}{\epsilon}))$ 次
  • 每次 BFS：$O(n^2)$
• 空间复杂度：$O(n)$

对于 $n \leq 3000$ 的数据规模，该算法能够高效运行。

样例验证

样例1：Boss在 $(2,2)$

• 最大距离为 $1.00$，因为 Boss 阻挡了中心区域

样例2：Boss在 $(3,1)$

• 最大距离为 $2.00$，可以贴着左侧和上侧边界绕过 Boss

该算法巧妙地利用二分答案和连通性判断，解决了复杂的几何路径规划问题。