P6455 不可视境界线[环版本]
题目背景
- 原题 : [P5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)
**附** : [关于本题的`SPJ`和数据的一些信息](https://www.luogu.com.cn/paste/tmwvh5vh)
若出现卡精度或数据出锅,吊打标算等情况,请联系出题人。
题目描述
有 $n$ 个半径为 $r$ 的圆,画在一个长度为 $L$ 的首尾相接的纸环上。
所有的圆心都在同一高度,可以看做在纸上画一个数轴然后卷起来,圆心的位置用这个数轴上的点描述。
如果无法理解纸环上圆的分布,可以查看样例解释以及子问题。
要求选出 $k$ 个圆,使得所有圆的并面积最大。
注意,您需要回答确切的选取方案而不是仅仅给出最大并面积。
输入格式
无
输出格式
无
说明/提示
**样例解释** :
- **样例1** : 最终的并面积约为 $565.871835$。
圆的分布如图所示,其中, $⊙A$ 和 $⊙A2$ 是同一个圆, $⊙B$ 和 $⊙B2$ 是同一个圆。
可以视作向右平移 $L=30$ 个单位长度而得,事实上就相当于在纸环上绕了一圈回到起点。
由于是同一个圆,被红色部分覆盖的面积不能重复计算,最大的并面积即为蓝色部分的面积。
- **样例2** : 最终的并面积约为 $942.477796$。
- **样例3** : 最终的并面积约为 $16817.058547$。
**数据范围与约定** :
| 子任务编号 | n | k | 时限 |
| :--: | :--: | :--: | :--: |
| 1 | $10$ | - | $\texttt{1s}$ |
| 2 | $100$ | - | $\texttt{1s}$ |
| 3 | $2000$ | - | $\texttt{1.6s}$ |
| 4 | $3\times 10^4$ | $100$ | $\texttt{2.2s}$ |
| 5 | $1\times 10^5$ | - | $\texttt{3s}$ |
时限在 `std` 耗时的两倍以上。
对于所有的数据, $n\leq 10^5$，$10\leq r\leq 2000$，$0\leq p[i]< L\leq 10^8$，$4r