首页 > 试题广场 >

圆覆盖

[编程题]圆覆盖

热度指数：1752 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 在二维平面中给出 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$ ，其点权为 $v_i$ 。你可以以原点 $(0,0)$ 为圆心放置一个圆。

$\hspace{15pt}$ 设圆的半径为 $r$ ，若某点满足 $x_i^2+y_i^2\leqq r^2$ ，则认为该点被圆覆盖。请你计算：
$\hspace{23pt}\bullet\,$ 要使被覆盖点的权值和不少于给定整数 $S$ ，所需的最小半径 $r$ 是多少？
$\hspace{15pt}$ 若无论半径多大都无法达到权值下限，则输出 $-1$ 。

输入描述:

第一行输入两个整数 ——点的数量与要求的权值下限。

接下来  行，第  行输入三个整数 ，描述第  个点的坐标与权值。

输出描述:

若存在可行半径，在一行输出该最小半径 ；否则输出 。

设你的输出为 ，答案为 。当且仅当



时，你的答案将被判定为正确。

示例1

输入

输出

说明

当半径为  时，、、、 四个点被覆盖，权值和为 ，达到要求。

示例2

输入

输出

-1

说明

权值和无法达到10

算法知识视频讲解

Mag1c0nch

发表于 2024-11-23 15:05:38

每个点到达圆心的距离固定，最终的半径也一定是某点到达圆心的距离，所以维护好每个点到圆心的距离和权值，按距离排序然后顺次选取即可，记得开ll #include <bits/stdc++.h> using namespace std; #define int long long const 展开全文

Silencer76

发表于 2025-08-13 16:24:06

题目链接圆覆盖题目描述在二维平面上给定个点，第个点的坐标为，其点权为。你需要以原点为圆心放置一个圆。设圆的半径为，若某点到原点的距离不大于（即），则该点被圆覆盖。请计算：要使被覆盖点的权值之和不少于给定的整数，所需的最小半径是多少？若无论半径多大都无法达到权值下展开全文

Kato_Shoko

发表于 2024-11-25 11:32:34

二分答案 #include <iostream> #include <queue> #include <map> #include <set> #include <cmath> #include <cstring> #inclu 展开全文

阿里嘎多懒羊羊桑_

发表于 2024-11-24 14:39:11

题意平面上有n个点，每个点有一个点权v。你现在可以以原点为圆心放置一个圆，请问要使圆能覆盖到的点的权值和达到x，圆的半径至少为多少？思路最小值问题先考虑下单调性点的点权为正整数，如果圆的半径增加，那么能覆盖的点会增大，权值和增大，具有单调性，所以可以二分圆的半径。对于check函数，需要判断在圆展开全文

wcy_sjtu

发表于 2025-08-12 10:13:26

直接按离原点距离排序，然后累加达到S后打印退出。注意用long来存储S，二分的提示可以忽略。 import java.util.*; class Point { int x,y,v; double d; Point(int x,int y,int v) { 展开全文

是基德吖

发表于 2024-11-25 14:15:08

import java.io.*; import java.util.*; import java.math.BigInteger; public class Main { static class Node { double x, y, v; Node( 展开全文

丨阿伟丨

发表于 2025-09-01 10:44:48

题目链接圆覆盖题目描述在二维平面上有个带权值的点。你需要以原点为圆心放置一个圆，半径为。如果一个点满足，则该点被圆覆盖。你需要找到一个最小的半径，使得所有被覆盖的点的权值之和不少于给定的整数。如果无论半径多大都无法达到权值下限，则输出 -1。解题思路这是一个求解满足特展开全文

Feijoa_Li

发表于 2024-11-25 21:07:50

#include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back #define endl "\n" #define x first #defin 展开全文

牛客242693846号

发表于 2025-07-31 15:09:34

from math import sqrt import bisect n, S = map(int, input().split()) points = [list(map(int, input().split())) for _ in range(n)] # 按到原点的距离排序 point 展开全文