[MtOI2019]不可视境界线

题目背景

「爆ぜろリアル!弾けろシナプス!パニッシュメント......ディス、ワールド!」 「爆裂吧,现实!粉碎吧,精神!放逐这个世界!」

题目描述

Rikka 坚信,她的父亲在「不可视境界线」中,等待着她的到来。在 Rikka 的梦里,「不可视境界线」出现了,那是 $n$ 个圆组成的图形。 具体地,有一个平面直角坐标系,坐标系的 $x$ 轴上有 $n$ 个点,第 $i$ 个点的坐标为 $(x_i,0)$。 Rikka 以每一个点作为圆心,作了 $n$ 个半径为 $r$ 的圆。她本想让你帮她计算这 $n$ 个圆的面积并,但是这个问题太简单了。 在一番思考后,Rikka 想让你计算出选出 $k$ 个圆后(即删除 $n-k$ 个圆),圆的面积并的最大值。 对于所有数据,有 $n,k\leq 10^5$,$r\leq 10^4$,$0\leq x_i\leq 10^9$,$x_i$ 为整数且不重复。保证输入的 $x_i$ 单调递增。 因为答案太大了,Rikka 考虑到你的电脑无法保持高精度,所以只要你的答案与标准答案的 **相对误差** 小于 $5\times 10^{-8}$,你的答案即被视为是正确的。 经过误差分析,本题保证使用原生 `cmath` 函数不会出错,请注意控制程序精度误差。

输入输出格式

输入格式


共 $2$ 行。 第 $1$ 行输入 $3$ 个整数 $n$,$k$,$r$。 第 $2$ 行输入 $n$ 个整数 $x_1\ldots x_n$。

输出格式


一行 $1$ 个实数,表示所求答案,保证答案小于 $10^{14}$。

输入输出样例

输入样例 #1

8 5 2
1 3 7 11 15 21 27 33

输出样例 #1

62.83185307

输入样例 #2

8 5 8
1 3 7 11 15 21 27 33

输出样例 #2

686.19551835

说明

#### 样例解释 1 显然,可以选出 $5$ 个不相交的半径为 $2$ 的圆。 ### 子任务 对于 $100\%$ 的数据,$n,k\leq 10^5$,$r\leq 10^4$,$0\leq x_i\leq 10^9$。 本题采用捆绑测试,共有 $7$ 个子任务,各子任务的分值和限制如下: 子任务 $1$($11$ 分):$k=n$。 子任务 $2$($13$ 分):$n,k,r \leq 100$。 子任务 $3$($6$ 分):$n,k \leq 1000$,$r\leq 20$。 子任务 $4$($15$ 分):$n,k,r \leq 2000$,保证数据随机生成。 子任务 $5$($23$ 分):$r\leq 20$。 子任务 $6$($12$ 分):$k\leq 20$,$x_n \leq kr$。 子任务 $7$($20$ 分):无特殊限制。 ### 题目来源 [MtOI2019 Extra Round](https://www.luogu.org/contest/22840) T5 出题人:disangan233 验题人:suwAKow,_sys