题目链接

圆覆盖

题目描述

在二维平面上给定 个点，第 个点的坐标为 ，其点权为 。你需要以原点 为圆心放置一个圆。

设圆的半径为 ，若某点到原点的距离不大于 （即 ），则该点被圆覆盖。

请计算：要使被覆盖点的权值之和不少于给定的整数 ，所需的最小半径 是多少？若无论半径多大都无法达到权值下限，则输出 -1。

输入:

  • 第一行输入两个整数 和 。
  • 接下来 行，每行输入三个整数 。

输出:

  • 若存在可行半径，在一行中输出该最小半径 （浮点数）。
  • 否则输出 -1。
  • 答案的精度要求为 。

解题思路

本题要求找到满足特定权值和条件的最小半径。我们可以观察到一个关键的单调性：随着圆的半径 增大，被覆盖的点的集合只会增加或不变，因此被覆盖点的权值总和是一个单调不减的函数。

这个性质通常指向二分查找的解法，但有一个更直接、更简单的贪心策略。

为了使半径最小，我们应该优先覆盖那些离原点最近的点。这启发我们应该按照点到原点的距离，从近到远地将它们逐个纳入圆中，直到权值总和满足要求。

为了避免浮点数计算带来的精度问题和性能开销，我们可以全程使用距离的平方进行比较和计算，只在最后输出时才进行开方操作。

算法步骤如下：

  1. 计算距离平方：对于每个点 ，计算它到原点距离的平方 。注意，由于 的范围可达 ，它们的平方会超过标准32位整数的范围，需要使用长整型（long long 或 long）来存储。
  2. 存储与排序：将每个点的距离平方 和其权值 作为一个数据对进行存储。然后，将所有这些数据对按照距离平方 进行升序排序。
  3. 累加权值：遍历排序后的点列表，逐个累加它们的权值。
  4. 寻找最小半径：在累加过程中，一旦权值总和首次达到或超过目标值 ，我们就可以停止。此时，我们刚刚加入的那个点，其到原点的距离就是我们所需要的最小半径。这个半径 就是该点距离平方的平方根，即 。
  5. 处理无解情况：如果遍历完所有点，累加的权值总和仍然小于 ，则说明无论半径多大都无法满足条件，此时应输出 -1。

这个贪心算法是正确的，因为它确保了在满足权值和条件的那一刻，我们所使用的半径是所有可能半径中最小的。

代码

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

using namespace std;

struct Point {
    long long dist_sq;
    int weight;
};

bool comparePoints(const Point& a, const Point& b) {
    return a.dist_sq < b.dist_sq;
}

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

    int n;
    long long k;
    cin >> n >> k;

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

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

    sort(points.begin(), points.end(), comparePoints);

    long long current_weight = 0;
    long long min_dist_sq = 0;

    for (const auto& p : points) {
        current_weight += p.weight;
        if (current_weight >= k) {
            min_dist_sq = p.dist_sq;
            break;
        }
    }

    cout << fixed << setprecision(7) << sqrt((long double)min_dist_sq) << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static class Point {
        long distSq;
        int weight;

        Point(long distSq, int weight) {
            this.distSq = distSq;
            this.weight = weight;
        }
    }

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

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

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

        Arrays.sort(points, Comparator.comparingLong(p -> p.distSq));

        long currentWeight = 0;
        long min_dist_sq = 0;

        for (Point p : points) {
            currentWeight += p.weight;
            if (currentWeight >= k) {
                min_dist_sq = p.distSq;
                break;
            }
        }

        System.out.printf("%.7f\n", Math.sqrt(min_dist_sq));
    }
}

import math

def solve():
    n, k = map(int, input().split())
    points = []
    total_weight = 0
    for _ in range(n):
        x, y, w = map(int, input().split())
        dist_sq = x * x + y * y
        points.append((dist_sq, w))
        total_weight += w

    if total_weight < k:
        print(-1)
        return

    points.sort()

    current_weight = 0
    min_dist_sq = 0
    
    for dist_sq, weight in points:
        current_weight += weight
        if current_weight >= k:
            min_dist_sq = dist_sq
            break
            
    print(f"{math.sqrt(min_dist_sq):.7f}")

solve()

算法及复杂度

  • 算法：贪心 + 排序
  • 时间复杂度：。算法的瓶颈在于对所有点按其到原点的距离平方进行排序。
  • 空间复杂度：，用于存储所有点的距离平方和权值。