自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:20:12，当前版本为作者最后更新于2020-04-20 20:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次首 A 一个黑题，要发题解纪念

毒瘤题，有卡精度有卡常数。。。

这道题目一看上来彻底没有思想，应为圆形不能用扫描线处理。然后，另一个可能想到的想法是随机挑一堆点，然后把这些点的覆盖概率加起来，但是这样不仅暴精度还是 $O(n^3)$，明显过不了。

正解：

假设对与一个线 $x=L$，这个线期望覆盖的长度为 $f(L)$。应为期望线性，如果我们可以计算 $f(L)$，那么答案为

这个可以用自适应辛普森法计算，代价是大概 $O(N\log N)$ 个 $f$ 计算。

怎么计算 $f$ 呢？对与任意一个平面上的点，如果这个点被 $i$ 个圆形覆盖了，这个点的被选的圆形覆盖了的概率为 $1-(\frac{N-1}{N})^K$。这是应为这个点没有被最终覆盖上需要在 $N-i$ 个剩下圆形重复选 $k$ 个，或者 $(N-i)^k$ 个方案；总共有 $N^k$ 个方案，点被覆盖了的概率就是 $1-(\frac{N-1}{N})^K$ 了。

（又）应为概率线性，如果统计一下这个线段上面有多长被恰好 $i$ 个圆形覆盖了，叫 $t_i$，那么有

这样，直接用扫描线处理 $t_i$ 就可以 $O(N)$ 计算 $f$，总共复杂度在 $O(N^2\log N)$ 左右，大力卡常就过了。