「BalticOI 2012 Day1」移动网络 题解

题目分析

这个问题要求我们找到高速公路上所有点到最近基站距离的最大值。高速公路是从 $(0,0)$ 到 $(L,0)$ 的线段，有 $N$ 个基站分布在平面上。

问题转化

对于给定的最大距离 $D$，我们需要判断：是否高速公路上每个点都至少被一个基站的覆盖范围（半径为 $D$ 的圆）所覆盖。

算法思路

1. 二分答案

使用二分法来寻找最小的 $D$，使得高速公路被完全覆盖：

• 下界：$l = 0$
• 上界：$r = 3 \times 10^9$（足够大以覆盖所有可能情况）

2. 检查函数 chk(D)

对于给定的 $D$，判断高速公路是否被完全覆盖：

关键观察：

• 基站 $(x_i, y_i)$ 能覆盖到高速公路上的区间为：$$[x_i - \sqrt{D^2 - y_i^2},\ x_i + \sqrt{D^2 - y_i^2}] $$
• 但前提是 $|y_i| \leq D$，否则基站无法覆盖到高速公路

算法步骤：

1. 初始化覆盖区间 $[L, R] = [0, 0]$
2. 遍历所有基站：
   • 如果 $|y_i| < D$，计算基站能覆盖的高速公路区间
   • 如果新区间与当前覆盖区间相连，则扩展覆盖区间
3. 判断最终覆盖区间是否包含整个 $[0, L]$

3. 复杂度分析

• 二分次数：$O(\log(\frac{3\times 10^9}{10^{-5}})) \approx O(35)$
• 每次检查：$O(N)$
• 总复杂度：$O(N \log \frac{r-l}{\epsilon})$，对于 $N \leq 10^6$ 可接受

代码实现要点

auto chk = [&](db D) {
    db L = 0, R = 0;  // 当前已覆盖的区间[0,R]
    For(i, 1, n) {
        if (b[i] < D) {  // b[i] = |y_i|
            db t = sqrt(D * D - 1.0 * b[i] * b[i]);
            db ll = a[i] - t, rr = a[i] + t;
            ll = max(ll, 0.0);  // 截断到高速公路范围内
            
            if (ll > rr) continue;  // 无效区间
            
            if (ll <= L) L = max(rr, R);  // 区间相连，扩展覆盖
            R = max(R, rr);  // 更新右端点
        }
    }
    return L >= Len && R >= Len;  // 检查是否完全覆盖
};

样例解析

对于样例：

2 10
0 0
11 1

• 基站1：$(0,0)$，覆盖区间 $[-D, D]$
• 基站2：$(11,1)$，覆盖区间 $[11-\sqrt{D^2-1}, 11+\sqrt{D^2-1}]$
• 通过二分找到 $D \approx 5.545$ 时，两个基站的覆盖区间能够连接起来覆盖 $[0,10]$

算法标签

🏷️ 主要算法

二分答案 (Binary Search on Answer)

• 在实数范围内二分查找最小覆盖半径
• 精度要求：误差不超过 $10^{-3}$

贪心区间覆盖 (Greedy Interval Covering)

• 将基站覆盖范围转化为区间覆盖问题
• 使用贪心策略合并相连区间

🏷️ 几何处理

圆与线段的相交 (Circle-Line Intersection)

• 计算基站覆盖圆在高速公路上的投影区间
• 使用勾股定理：$\text{半径} = \sqrt{D^2 - y_i^2}$

🏷️ 优化技术

预处理优化

• 预先计算 $|y_i|$，避免重复计算绝对值
• 利用输入已排序的性质（虽然本题解中未显式利用）

数值稳定性

• 处理 $|y_i| \geq D$ 的情况，避免复数运算
• 合理的上界选择确保二分收敛

🏷️ 复杂度类别

线性对数级别

• 时间复杂度：$O(N \log \frac{r-l}{\epsilon})$
• 空间复杂度：$O(N)$

这个问题的核心在于将几何覆盖问题转化为区间覆盖问题，通过二分答案 + 贪心验证的方法高效求解，是典型的"最小值最大化"问题。