题解 | #圆覆盖#

问题分析

该问题的核心是在二维平面内寻找一个以原点 为圆心的最小半径 ，使得落在此闭圆盘区域内的点权之和达到预设阈值 。

1. 单调性（Monotonicity）：覆盖点的权值之和与圆的半径 之间存在非减的函数关系。即随着 的增大，被覆盖的点集是单调不减的，因此权值和也是单调不减的。
2. 离散决策点（Discrete Candidate Values）：最优半径 必然等于原点到某个现有落点 的欧几里得距离。因为在两个相邻距离之间增加半径，并不会包含更多的点，也就不会改变权值和。
3. 计算精度：输出要求相对误差小于 ，这意味着我们需要在计算距离平方时保持精度，并最终进行开方运算。

算法：排序与前缀和

基于上述性质，最直接且高效的策略是离散化处理结合极坐标距离排序。我们不需要在连续空间内搜索 ，而是将所有候选的半径（即各点到原点的距离）提取出来进行处理。

核心思路

1. 欧氏距离平方化：为了避免早期开方带来的精度损失以及提高计算效率，我们直接计算每个点到原点的距离平方 。
2. 排序：将所有点按照其 从小到大进行排序。
3. 扫描与累加：顺序遍历排序后的点，累加其权值 。当权值和首次达到或超过 时，当前点的距离平方 对应的半径 即为所求。

复杂度分析

• 时间复杂度：
  • 计算所有点的距离平方：。
  • 对 个点进行排序：典型的 瓶颈。
  • 线性扫描累加权值：。
• 空间复杂度：
  • 需要存储每个点的距离平方及其对应的权值，空间占用与 成线性关系。

代码实现

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

struct Circle {
    ll x, y;
    ll v;
};

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

    int n;
    ll S;
    cin >> n >> S;

    vector<Circle> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].v;
    }

    sort(c.begin(), c.end(), [](const Circle & a, const Circle & b) {
        return (a.x * a.x + a.y * a.y) < (b.x * b.x + b.y * b.y);
    });

    vector<ll> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + c[i - 1].v;
    }

    auto it = lower_bound(prefix.begin(), prefix.end(), S);
    if (it == prefix.end()) {
        cout << -1 << endl;
        return 0;
    }
    int idx = std::distance(prefix.begin(), it) - 1;
    double r = sqrt(c[idx].x * c[idx].x + c[idx].y * c[idx].y);
    cout << fixed << setprecision(10) << r << endl;
}