题解 | 牛牛战队的比赛地

https://ac.nowcoder.com/acm/contest/120458/B

对于位于 X = (X,0) 的比赛地点，到训练基地Pi = (xi , yi) , i = 1 … N

的距离为disti (X) = sqrt( (X – xi)² + yi² )

这些距离中的最大值（我们需要最小化的值）为F(X) = max_i disti (X)

比赛场地必须位于 x 轴上，因此我们只能改变 X。

1. 从“最小化最大值”到区间问题

对于给定的数 R ( ≥ 0 )，

disti (X) ≤ R    ⇔   (X – xi)² + yi² ≤ R²
                ⇔   (X – xi)² ≤ R² – yi²

• 如果 R < |yi|，则右边为负数——此时条件永远无法满足。
• 否则X ∈ [ xi – √(R² – yi²) , xi + √(R² – yi²) ] (1)

对于一个固定的 R，整个区间集合 (1) 存在一个公共点 当且仅当 这些区间本身的交集非空。

因此存在满足 max_i disti (X) ≤ R 的 X ⇔ 来自 (1) 的区间存在交集

因此，原问题转化为：

寻找最小的 R，使得所有区间 [xi – Δi , xi + Δi ] 有交集，其中
           Δi = √(R² – yi²)    （如果 R ≥ |yi|，否则区间为空）

2. 检查给定的 R

对于一个具体的 R≥0，

L = –∞ , U = +∞
对于每个基地 i
        如果 R < |yi| → 不可能
        dx = sqrt(R*R – yi*y)
        left  = xi – dx
        right = xi + dx
        L = max(L , left)          // 所有 left 边中的最右端
        U = min(U , right)         // 所有 right 边中的最左端
        如果 L > U → 不可能
如果循环结束后 ⇒ 可能   （交集 = [L , U]）

该测试的时间复杂度为 O(N)。

3. 搜索最优的 R

函数feasible(R) = “区间存在非空交集”

是单调的：如果对于某个 R 它是 true，则对于任意更大的 R 也保持为 true。

因此可以在 R 上进行二分查找。

一个显然的下界是low = max_i |yi|

（即使将比赛地点恰好设在基地 i 所在 x 坐标处，其距离也至少为 |yi|）。

一个安全的上界为high = 30000 // 因为 |xi|,|yi| ≤ 10 000

如果 high 不够大（在给定的限制下不应发生），我们就将 high 加倍，直到它变为可行。

现在执行经典的二分搜索：

重复 60–70 次               // 足以达到 1e‑6 的精度
        mid = (low + high)/2
        if feasible(mid)   high = mid
        else               low  = mid

答案为 high（或 low——两者相差不超过 high‑low）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> x(N);
    vector<int> y(N);
    double maxAbsY = 0.0;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        maxAbsY = max(maxAbsY, fabs(y[i]));
    }

    auto check = [&](double r) -> bool {
        double L = -numeric_limits<double>::max();
        double R = numeric_limits<double>::max();
        for (int i = 0; i < N; i++) {
            if (r < fabs(y[i]))
                return false;
            double delta = sqrt(r * r - y[i] * y[i]);
            L = max(L, x[i] - delta);
            R = min(R, x[i] + delta);
            if (L > R)
                return false;
        }
        return true;
    };

    double epsilon = 1e-6;
    double low = maxAbsY;
    double high = 30000;

    while (high - low >= epsilon) {
        double mid = (low + high) / 2.0;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }

    cout << fixed << setprecision(10) << high << endl;
}