圆覆盖【牛客tracker 每日一题】

圆覆盖时间限制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^2y_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_i2^{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 234110234110达到要求。示例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的大数据规模精准且高效。总结核心逻辑按点到原点的距离升序排列通过前缀和快速找到满足权值要求的最小半径。关键操作计算距离平方排序线性累加权值判断阈值对合法半径开方输出。效率保障排序线性遍历无冗余计算全程用整数运算避免精度丢失。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;structnode{ll r_2,v;}d[N];boolcmp(node a,node b){returna.r_2b.r_2;}intmain(){ll n,s;cinns;for(ll i1;in;i){ll x,y;cinxyd[i].v;d[i].r_2x*xy*y;}sort(d1,dn1,cmp);ll sum0;for(ll i1;in;i){sumd[i].v;if(sums){printf(%.6lf,sqrt(d[i].r_2));return0;}}cout-1endl;return0;}