题目背景

• 原题 : P5617 [MtOI2019]不可视境界线

附 : 关于本题的SPJ和数据的一些信息

若出现卡精度或数据出锅,吊打标算等情况,请联系出题人。

题目描述

有 $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}$ 量级。

5 3 10 30
0 7 14 21 28 

2 3 5 

10 3 10 65
0 7 15 24 30 36 41 49 57 63 

3 6 9

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 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$
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$。

表格中均为上界。注意,一些下界限制可能帮助省去了问题的某些边界情况。