题解 | #圆覆盖#

题目链接

圆覆盖

题目描述

在二维平面上有 $N$ 个带权值的点 $(x_i, y_i, v_i)$ 。你需要以原点 $(0,0)$ 为圆心放置一个圆，半径为 $r$ 。

如果一个点满足 $x_i^2 + y_i^2 \le r^2$ ，则该点被圆覆盖。

你需要找到一个最小的半径 $r$ ，使得所有被覆盖的点的权值之和不少于给定的整数 $S$ 。如果无论半径多大都无法达到权值下限，则输出 -1。

解题思路

这是一个求解满足特定条件的最小值问题，并且该条件具有明显的单调性，因此非常适合使用二分答案的方法。

1. 单调性分析

我们要求的是最小半径 $r$ 。可以观察到，当半径 $r$ 增大时，被圆覆盖的点的集合是只增不减的，因此这些点的权值之和也是一个单调非递减的函数。

换句话说，如果一个半径 $r$ 能够满足“权值和不小于 $S$ ”的条件，那么任何大于 $r$ 的半径也一定能满足该条件。这种单调性是使用二分答案的前提。

2. 二分答案框架

我们可以在一个足够大的半径范围内对答案 $r$ 进行二分查找。

check(r) 函数：我们需要一个辅助函数 check(r)，用于判断给定的半径 $r$ 是否可行。
- 该函数的逻辑是：计算所有被半径为 $r$ 的圆覆盖的点的权值之和。
- 遍历所有 $N$ 个点，对于每个点 $(x_i, y_i)$ ，计算其到原点距离的平方 $d_i^2 = x_i^2 + y_i^2$ 。
- 为了避免浮点数精度问题，我们比较距离的平方：如果 $d_i^2 \le r^2$ ，则将该点的权值 $v_i$ 累加。
- 最后，如果累加的总权值大于或等于 $S$ ，则 check(r) 返回 true，否则返回 false。
二分过程：
- 我们设定一个二分区间，左边界 $L=0$ ，右边界 $R_{max}$ 可以取一个足够大的值（例如 $2 \cdot 10^9$ ，因为坐标最大为 $10^9$ ）。
- 在循环中（通常进行固定次数如100次以保证精度），取中点 $mid = L + (R_{max}-L)/2$ 。
- 如果 check(mid) 为 true，说明半径 $mid$ 是一个可行的解，但可能不是最小的。我们记录下这个解，并尝试在更小的范围 $[L, mid]$ 中寻找更优解。
- 如果 check(mid) 为 false，说明半径 $mid$ 太小，必须增大。我们在范围 $[mid, R_{max}]$ 中继续寻找。
初始判断：在开始二分前，应先计算所有点的权值总和。如果总和小于 $S$ ，则不可能满足条件，直接输出 -1。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct Point {
    long long x, y, v;
};

// 检查半径 r 是否满足条件
bool check(double r, long long S, int n, const vector<Point>& points) {
    long long current_weight = 0;
    double r_sq = r * r;
    for (int i = 0; i < n; ++i) {
        long long d_sq = points[i].x * points[i].x + points[i].y * points[i].y;
        if (d_sq <= r_sq) {
            current_weight += points[i].v;
        }
    }
    return current_weight >= S;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long S;
    cin >> n >> S;

    vector<Point> points(n);
    long long total_weight = 0;
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y >> points[i].v;
        total_weight += points[i].v;
    }

    if (total_weight < S) {
        cout << -1 << endl;
        return 0;
    }

    double left = 0.0, right = 2e9; // 一个足够大的半径上界
    // 进行100次二分以保证精度
    for(int i = 0; i < 100; ++i) {
        double mid = left + (right - left) / 2.0;
        if (check(mid, S, n, points)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    cout << fixed << setprecision(10) << right << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static class Point {
        long x, y, v;
    }

    // 检查半径 r 是否满足条件
    private static boolean check(double r, long S, int n, Point[] points) {
        long currentWeight = 0;
        double rSq = r * r;
        for (int i = 0; i < n; i++) {
            long dSq = points[i].x * points[i].x + points[i].y * points[i].y;
            if (dSq <= rSq) {
                currentWeight += points[i].v;
            }
        }
        return currentWeight >= S;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long S = sc.nextLong();

        Point[] points = new Point[n];
        long totalWeight = 0;
        for (int i = 0; i < n; i++) {
            points[i] = new Point();
            points[i].x = sc.nextLong();
            points[i].y = sc.nextLong();
            points[i].v = sc.nextLong();
            totalWeight += points[i].v;
        }

        if (totalWeight < S) {
            System.out.println(-1);
            return;
        }

        double left = 0.0, right = 2e9; // 一个足够大的半径上界
        // 进行100次二分以保证精度
        for (int i = 0; i < 100; i++) {
            double mid = left + (right - left) / 2.0;
            if (check(mid, S, n, points)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        System.out.printf("%.10f\n", right);
    }
}

import math

def check(r, S, n, points):
    current_weight = 0
    r_sq = r * r
    for x, y, v in points:
        d_sq = x * x + y * y
        if d_sq <= r_sq:
            current_weight += v
    return current_weight >= S

def main():
    n, S = map(int, input().split())
    points = []
    total_weight = 0
    for _ in range(n):
        x, y, v = map(int, input().split())
        points.append((x, y, v))
        total_weight += v

    if total_weight < S:
        print(-1)
        return

    left, right = 0.0, 2e9  # 一个足够大的半径上界
    
    # 进行100次二分以保证精度
    for _ in range(100):
        mid = (left + right) / 2.0
        if check(mid, S, n, points):
            right = mid
        else:
            left = mid
            
    print(f"{right:.10f}")

if __name__ == "__main__":
    main()

算法及复杂度

算法：实数域二分答案。
时间复杂度： $O(N \cdot K)$ ，其中 $N$ 是点的数量， $K$ 是二分次数（为了保证精度，通常取一个固定的值，如 100）。check 函数每次调用需要 $O(N)$ 的时间。
空间复杂度： $O(N)$ ，用于存储 $N$ 个点的信息。