首页 > 试题广场 >

圆覆盖

[编程题]圆覆盖
  • 热度指数：2068 时间限制：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。

输入描述:
\hspace{15pt}第一行输入两个整数 n,S\left(1\leqq n\leqq10^5,\ 1\leqq S\leqq10^{14}\right)——点的数量与要求的权值下限。

\hspace{15pt}接下来 n 行，第 i 行输入三个整数 x_i,y_i,v_i\ \left(-10^9\leqq x_i,y_i\leqq10^9,\ 0\leqq v_i<2^{31}\right)，描述第 i 个点的坐标与权值。


输出描述:
\hspace{15pt}若存在可行半径，在一行输出该最小半径 r；否则输出 -1。

\hspace{15pt}设你的输出为 a，答案为 b。当且仅当

\displaystyle \frac{|a-b|}{\max\bigl(1,|b|\bigr)}<10^{-6}

\hspace{15pt}时，你的答案将被判定为正确。
示例1

输入

5 10
0 1 2
-1 1 3
3 3 4
-4 3 1
5 -3 1

输出

5

说明

当半径为 5 时，(0,1)、(-1,1)、(3,3)、(-4,3) 四个点被覆盖，权值和为 2+3+4+1=10，达到要求。
示例2

输入

5 10
0 1 2
-1 1 3
3 3 2
-4 3 1
5 -3 1

输出

-1

说明

权值和无法达到10
算法知识视频讲解
添加回答
C++
讲原则的秋招侠在备战秋招头像 讲原则的秋招侠在备战秋招
怎么就能输出0呢 
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() 
{
    int n,s;
    std::cin>>n>>s;

    long long x,y,v;
    long long total=0;
    std::map<long long,int> mymap;
    for(int i=0;i<n;++i)
    {
        std::cin>>x>>y>>v;
        total+=v;
        mymap[x*x+y*y]+=v;
    }
    double ans = 0;
    if(total<s)
        ans = -1;
    else
    {
        total=0;
        for(auto& data : mymap)
        {
            total += data.second;
            if(total>=s)
            {
                ans=std::sqrt(data.first);
                break;
            }
        }
    }
    std::cout<<ans<<"\n";
}

发表于 2026-01-13 10:56:42 回复(0)
Python3
牛客143314440号头像 牛客143314440号
print(f"{r:.7f}")
自测用例过不了但是能ac。荒谬。
发表于 2025-10-19 15:13:02 回复(1)
提交观点

问题信息

来自：华为机试编程模拟题9
难度：
2条回答 526浏览

热门推荐

相关试题

圆覆盖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号