题解：POI 2011 Plot

问题简化

给定 n 个点 P₁...Pₙ，分成 ≤m 个连续段

每段用一个新点 Qᵢ 代替段内所有点

定义相似度为 max(段内点与对应 Qᵢ 的距离)

目标：最小化相似度

核心思路

二分答案 + 贪心验证 + 最小圆覆盖

步骤1：二分答案 二分搜索最小相似度 d，检查能否用 ≤m 段覆盖所有点，使每段点都能被半径为 d 的圆覆盖。

步骤2：检查可行性（check函数） 给定半径 d，贪心地构造段：

从当前点开始，尝试扩展段直到不能用一个半径 d 的圆覆盖段内所有点

需要快速判断：一段点能否被半径 d 的圆覆盖 → 转化为找最小圆覆盖半径是否 ≤d

优化：对于连续点序列 Pₗ...Pᵣ，求最小圆覆盖可以：

用 Welzl 算法 O(r-l+1) 计算

但需要多次调用 → 用倍增优化：

固定起点 l，用倍增找最远的 r 使最小圆半径 ≤d

这样每段只需 O(k log n) 时间，其中 k 是段长

步骤3：构造方案 二分得到最小 d 后，用同样的贪心+最小圆覆盖构造具体分段和 Q 点坐标。

算法流程

text

1. 二分 d ∈ [0, 最大两点距离]
2. check(d): cnt = 0, i = 1 while i <= n: cnt++ 用倍增找到以 i 起点的最长段使最小圆半径 ≤d i = r + 1 return cnt ≤ m
3. 二分得到最小 d
4. 用 check 的方法构造分段，每段计算最小圆圆心作为 Q 时间复杂度 每次 check: O(n log n × 最小圆覆盖时间)

最小圆覆盖用随机增量法 O(k) 每段

总复杂度 O(n log n log(坐标范围/精度))

关键细节

精度要求高，二分时 eps = 1e-7

最小圆覆盖用 Welzl 随机算法

输出保留足够小数位