问题分析

我们需要在 $n \times m$ 的矩形通道中找到一条从左边界到右边界的路径，使得路径上距离所有星星和上下边界的最小距离最大化。

这是一个典型的最大化最小值问题，可以通过二分答案或最小生成树的思路解决。

算法思路

核心思想：最小生成树 + 虚拟边界点

将问题转化为图论问题：

• 每个星星是一个节点
• 添加两个虚拟节点：上边界和下边界
• 构建完全图，边权为星星之间的距离
• 找到从上边界到下边界路径上的最大边权的最小值

关键观察

1. 路径障碍：星星和边界形成"障碍"，路径必须从它们之间的缝隙通过
2. 瓶颈效应：路径的通过能力由最窄的缝隙决定
3. 对偶转化：最大化最小距离 ⇔ 找到连接上下边界的"瓶颈"

代码详解

1. 数据结构定义

struct Point {
    double x, y;
} stars[MAXN];
double min_distance[MAXN];  // 存储每个点到生成树的最小距离
bool visited[MAXN];         // 标记点是否已加入生成树

2. 改进的Prim算法

使用优先队列优化的Prim算法构建最小生成树：

void prim() {
    // 初始化：每个点到上边界的距离
    for (int i = 1; i <= k; i++) {
        min_distance[i] = m - stars[i].y;  // 到上边界的距离
    }
    min_distance[k + 1] = m;  // 虚拟点（下边界）的初始距离
    
    // 优先队列优化
    priority_queue<pair<double, int>, vector<pair<double, int>>, 
                   greater<pair<double, int>>> pq;
    
    for (int i = 1; i <= k + 1; i++) {
        pq.push({min_distance[i], i});
    }
    
    while (!pq.empty()) {
        auto [d, x] = pq.top();
        pq.pop();
        
        if (visited[x]) continue;
        visited[x] = true;
        ans = max(ans, d);  // 更新答案
        
        if (x == k + 1) return;  // 到达下边界，结束
        
        // 更新其他星星的距离
        for (int j = 1; j <= k; j++) {
            if (!visited[j]) {
                double new_distance = distance(stars[j], stars[x]);
                if (new_distance < min_distance[j]) {
                    min_distance[j] = new_distance;
                    pq.push({min_distance[j], j});
                }
            }
        }
        
        // 更新虚拟点到下边界的距离
        if (stars[x].y < min_distance[k + 1]) {
            min_distance[k + 1] = stars[x].y;
            pq.push({min_distance[k + 1], k + 1});
        }
    }
}

3. 距离计算

double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + 
                (a.y - b.y) * (a.y - b.y));
}

4. 主函数

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d%d", &x, &y);
        stars[i].x = x;
        stars[i].y = y;
    }
    
    prim();
    printf("%.9lf\n", ans / 2.0);  // 输出结果除以2
    return 0;
}

算法原理

虚拟节点的意义

• 上边界：初始时每个星星到上边界的距离为 m - y
• 下边界（节点 k+1）：初始距离为 m，在算法过程中更新为当前星星的 y 坐标

最小生成树的构建过程

1. 初始化：所有节点到上边界的距离
2. 逐步扩展：每次选择距离当前生成树最近的点加入
3. 答案更新：记录加入每个点时对应的距离
4. 终止条件：当下边界节点加入生成树时停止

最终答案的含义

当算法终止时，ans 表示连接上下边界的路径上的最大边权。由于路径可以在两个障碍的中间通过，实际可达到的最小距离最大值为 ans / 2。

正确性证明

最小生成树性质

在最小生成树中，连接任意两点的路径上的最大边权是所有路径中最小的。

虚拟边界的处理

• 上边界到星星的边权：m - y
• 星星到下边界的边权：y
• 这些边确保了边界也被考虑在内

答案除2的合理性

对于两个距离为 d 的障碍，最优路径可以从它们正中间通过，获得 d/2 的距离。

复杂度分析

时间复杂度

• 距离计算：$O(k^2)$，但通过优先队列优化为 $O(k^2 \log k)$
• 在 $k \leq 6000$ 时可行

空间复杂度

• $O(k^2)$：存储距离信息（隐式）
• $O(k)$：显式存储的数组

样例分析

对于样例：

n=10, m=5, k=2
星星: (1,1), (2,3)

• 两个星星之间的距离：$\sqrt{(1-2)^2 + (1-3)^2} = \sqrt{5} \approx 2.236$
• 到边界的距离：第一个星星到上边界为4，到下边界为1
• 最小生成树路径上的最大边权约为2.236
• 最终答案：$2.236 / 2 \approx 1.118$

算法优势

1. 正确性保证：基于最小生成树的理论基础
2. 高效实现：优先队列优化Prim算法
3. 精度控制：直接计算避免二分答案的迭代
4. 思路巧妙：虚拟边界点的引入简化问题

总结

本题通过将几何问题转化为图论问题，利用最小生成树的性质优雅地解决了最大化最小值问题。算法的核心创新在于：

• 将星星和边界统一建模为图中的节点
• 利用最小生成树找到连接边界的瓶颈路径
• 通过距离除以2得到实际可达到的最大最小距离

该解法体现了图论在几何问题中的应用，展示了不同数学领域之间的内在联系。