题解 | 圆覆盖

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
const double eps = 1e-6;
const int N = 1e5 + 9;
double a[N][3], n, S; 


//最短半径(下标)越大，得到的权值和(值)越大（单调递增）
//已知最短半径可以在O(n)时间算出覆盖的权值和
//找出分界点（即在权值和至少为S时最短半径）

//示例（以整数为例）
//半径     1  2  3  4
//权值和   0  1  1  2
//如果S为1时，半径最短为2，也就是找到第一个值>=1的位置下标（左边界二分）

//根据下标得到值（由半径得到权值和）
double check(double mid){
    double res = 0;
    for(int i = 0; i < n; ++i){
        double dist = a[i][0] * a[i][0] + a[i][1] * a[i][1];
        if(dist <= mid * mid){
            res += a[i][2];
        }
    }
    return res;
}


//二分答案（求什么分什么），分实数半径r
int main() {
    cin >> n >> S;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 3; ++j){
            cin >> a[i][j];
        }
    }

    //二分最短半径
    double l = 0, r = 1e10; //根据x,y取值，半径r最大不超过根号2*1e9 < 1e10
    while(r - l >= eps){
        double mid = l + (r - l) / 2;
        if(check(mid) >= S) r = mid;
        else l = mid;
    }
    cout << setprecision(10) << (check(r) >= S ? r : -1) << endl;
}