不可视境界线[环版本]
题目背景
- 原题 : [P5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)
**附** : [关于本题的`SPJ`和数据的一些信息](https://www.luogu.com.cn/paste/tmwvh5vh)
若出现卡精度或数据出锅,吊打标算等情况,请联系出题人。
题目描述
有 $n$ 个半径为 $r$ 的圆,画在一个长度为 $L$ 的首尾相接的纸环上。
所有的圆心都在同一高度,可以看做在纸上画一个数轴然后卷起来,圆心的位置用这个数轴上的点描述。
如果无法理解纸环上圆的分布,可以查看样例解释以及子问题。
要求选出 $k$ 个圆,使得所有圆的并面积最大。
注意,您需要回答确切的选取方案而不是仅仅给出最大并面积。
输入输出格式
输入格式
第一行包含四个整数 $n,k,r,L$ ,意义如题目所述。
第二行包含 $n$ 个整数,第 $i$ 个整数 $p[i]$ 描述了第 $i$ 个圆心在纸环上的位置(数轴上的坐标)。
对于 $2<i<n$ ,有 $p[i-1]<p[i]$。
输出格式
一行包含 $k$ 个整数,分别表示您选取的圆的编号,由`SPJ`来计算并面积。
您需要保证这些编号严格递增,并且在 $[1,n]$ 以内,否则被认为不合法而不得分。
与标准答案**相对误差**不超过 $10^{-9}$ ,**且绝对误差**不超过 $0.1$ 则认为正确。
通过估算,答案不会超过 $10^{12}$ 量级。
输入输出样例
输入样例 #1
5 3 10 30
0 7 14 21 28 输出样例 #1
2 3 5 输入样例 #2
10 3 10 65
0 7 15 24 30 36 41 49 57 63 输出样例 #2
3 6 9输入样例 #3
30 10 50 169
0 7 14 21 28 35 42 45 51 55 61 65 68 75 79 83 87 94 97 105 113 118 126 133 140 147 151 156 163 167 输出样例 #3
3 5 8 11 15 19 21 24 27 30 说明
**样例解释** :
- **样例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<L$，$3\leq k \leq n$。
表格中均为上界。注意,一些下界限制可能帮助省去了问题的某些边界情况。