圆覆盖
时间限制：3秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
在二维平面中给出n nn个点，第i ii个点的坐标为( x i , y i ) (x_i,y_i)(xi,yi)，其点权为v i v_ivi。你可以以原点( 0 , 0 ) (0,0)(0,0)为圆心放置一个圆。
设圆的半径为r rr，若某点满足x i 2 + y i 2 ≦ r 2 x_i^2+y_i^2≦r^2xi2+yi2≦r2，则认为该点被圆覆盖。请你计算：
- 要使被覆盖点的权值和不少于给定整数S SS，所需的最小半径r rr是多少？
若无论半径多大都无法达到权值下限，则输出− 1 −1−1。
输入描述：
第一行输入两个整数n , S ( 1 ≦ n ≦ 10 5 , 1 ≦ S ≦ 10 14 ) n,S(1≦n≦10^5, 1≦S≦10^{14})n,S(1≦n≦105,1≦S≦1014)——点的数量与要求的权值下限。
接下来n nn行，第i ii行输入三个整数x i , y i , v i ( − 10 9 ≦ x i , y i ≦ 10 9 , 0 ≦ v i < 2 31 ) x_i,y_i,v_i (−10^9≦x_i,y_i≦10^9, 0≦v_i<2^{31})xi,yi,vi(−109≦xi,yi≦109,0≦vi<231)，描述第 ii个点的坐标与权值。
输出描述：
若存在可行半径，在一行输出该最小半径r rr；否则输出− 1 −1−1。
设你的输出为a aa，答案为b bb。当且仅当
∣ a − b ∣ m a x ( 1 , ∣ b ∣ ) ∣ < 10 − 6 \frac{∣a−b∣}{max(1,∣b∣)}∣<10^{−6}max(1,∣b∣)∣a−b∣∣<10−6
时，你的答案将被判定为正确。
示例1
输入：
5 10 0 1 2 -1 1 3 3 3 4 -4 3 1 5 -3 1输出：
5说明：
当半径为5 55时，( 0 , 1 ) (0,1)(0,1)、( − 1 , 1 ) (−1,1)(−1,1)、( 3 , 3 ) (3,3)(3,3)、( − 4 , 3 ) (−4,3)(−4,3)四个点被覆盖，权值和为2 + 3 + 4 + 1 = 10 2+3+4+1=102+3+4+1=10，达到要求。
示例2
输入：
5 10 0 1 2 -1 1 3 3 3 2 -4 3 1 5 -3 1输出：
-1说明：
权值和无法达到10 1010
解题思路
本题核心是排序+前缀和求解最小覆盖半径，规避浮点运算误差。以原点为圆心的圆覆盖点的判定条件为：点到原点的距离平方≤ ≤≤半径平方。因此先计算每个点到原点的距离平方，将所有点按距离平方升序排序。遍历排序后的点，累加权值计算前缀和，当累加和首次≥目标值S时，当前点的距离平方开平方即为最小半径。若遍历完所有点，总权值和仍小于S SS，说明无法满足要求，输出− 1 -1−1。算法时间复杂度为O ( n log n ) O(n\log n)O(nlogn)，完美适配n ≤ 10 5 n≤10^5n≤105的大数据规模，精准且高效。
总结
核心逻辑：按点到原点的距离升序排列，通过前缀和快速找到满足权值要求的最小半径。
关键操作：计算距离平方排序，线性累加权值判断阈值，对合法半径开方输出。
效率保障：排序+线性遍历，无冗余计算，全程用整数运算避免精度丢失。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;structnode{ll r_2,v;}d[N];boolcmp(node a,node b){returna.r_2<b.r_2;}intmain(){ll n,s;cin>>n>>s;for(ll i=1;i<=n;i++){ll x,y;cin>>x>>y>>d[i].v;d[i].r_2=x*x+y*y;}sort(d+1,d+n+1,cmp);ll sum=0;for(ll i=1;i<=n;i++){sum+=d[i].v;if(sum>=s){printf("%.6lf",sqrt(d[i].r_2));return0;}}cout<<-1<<endl;return0;}
