BISHI86　圆覆盖¶

中等通过率 31.41%python3样例通过牛客 AC

牛客原题　源码

讲解章节：二分、计算几何入门

一句话

以原点为心的圆，求覆盖权值和 >= S 的最小半径。

解题思路¶

这题考什么¶

「答案单调 -> 排序 + 前缀和」的经典套路。半径 r 越大覆盖的点越多、权值和单调不减，所以答案具有单调性；而真正的最优半径一定恰好等于某个点到原点的距离（再小就会丢掉那个点，再大是浪费）。

于是做法是：

对每个点算 d2 = x^2 + y^2（全程用整数平方，不开根，避免浮点误差）；
按 d2 升序排序，求权值前缀和；
找到第一个前缀和 >= S 的位置 i，答案就是 sqrt(d2[i])；若总权值和 < S，输出 -1。

第 3 步既可以 bisect 也可以线性扫，这里线性扫更直白。前缀和的基本用法见 42-前缀和与差分。

数据规模与复杂度¶

n <= 1e5，排序 O(n log n)，其余 O(n)。 S <= 1e14、v_i < 2^31 -> 权值和最大 1e5 * 2^31 ≈ 2e14，C++ 需要 long long， Python 天然大整数无需担心。

坑在哪¶

不要对 r 做实数二分再去数点——那是 O(n log(1/eps))，又慢又有精度问题；排序法直接给出精确的 d2，只在最后开一次根号；
x, y <= 1e9 -> d2 最大 2e18，超过 2^31 甚至接近 2^63，必须用 64 位整数（Python 自动）。math.sqrt 接收这个大小的整数会转成 double，相对误差约 1e-16，开根后仍远优于题目要求的 1e-6；
v_i 可以是 0：权值为 0 的点不会成为「第一个使前缀和达标」的位置（因为它不改变前缀和），所以不会导致答案偏大，逻辑天然正确；
无解时输出 -1（整数），不要输出 -1.000000 之外的奇怪格式；有解时按题目允许 1e-6 相对误差，输出 6 位小数即可。

参考实现¶

solutions/BISHI86.py
import sys
from math import sqrt


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); S = int(data[1])

    pts = []
    p = 2
    for _ in range(n):
        x = int(data[p]); y = int(data[p + 1]); v = int(data[p + 2]); p += 3
        pts.append((x * x + y * y, v))    # 用距离平方排序，整数无精度损失
    pts.sort()                        # 按距离平方升序，等价于按半径从小到大

    # 半径由小到大扫过每个点，权值前缀和第一次达标的位置就是最小可行半径
    acc = 0
    for d2, v in pts:
        acc += v
        if acc >= S:
            sys.stdout.write("%.6f\n" % sqrt(d2))   # 全程只在这里开一次根号
            return
    sys.stdout.write("-1\n")            # 把全部点都圈进来仍凑不够 S


main()

BISHI86 圆覆盖¶