首页 > 试题广场 >

圆覆盖

[编程题]圆覆盖
  • 热度指数：1313 时间限制：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
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

相关试题

圆覆盖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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