Background

「爆ぜろリアル！弾けろシナプス！パニッシュメント......ディス、ワールド！」
「Explode, reality! Shatter, mind! Banish this world!」

Problem Description

Rikka firmly believes that her father is waiting for her inside the “Invisible Boundary Line”. In Rikka’s dream, the “Invisible Boundary Line” appeared as a figure made up of $n$ circles.

Specifically, there is a Cartesian coordinate system. On the $x$-axis, there are $n$ points, and the $i$-th point is $(x_i,0)$.

Using each point as a center, Rikka drew $n$ circles with radius $r$. She originally wanted you to help her compute the union area of these $n$ circles, but that problem is too easy.

After some thought, Rikka wants you to compute the maximum possible union area of the circles after selecting $k$ circles (i.e., deleting $n-k$ circles).

For all testdata, $n,k\leq 10^5$, $r\leq 10^4$, $0\leq x_i\leq 10^9$, $x_i$ are integers and pairwise distinct. It is guaranteed that the input $x_i$ are strictly increasing.

Because the answer is very large, and Rikka thinks your computer cannot maintain high precision, your answer will be considered correct as long as its relative error is less than $5\times 10^{-8}$ compared to the standard answer.

After error analysis, this problem guarantees that using the native cmath functions will not cause issues. Please pay attention to controlling precision errors in your program.

Input Format

There are $2$ lines in total.

Line $1$ contains $3$ integers $n$, $k$, and $r$.

Line $2$ contains $n$ integers $x_1\ldots x_n$.

Output Format

Output one real number in one line, representing the required answer. It is guaranteed that the answer is less than $10^{14}$.

8 5 2
1 3 7 11 15 21 27 33

62.83185307

8 5 8
1 3 7 11 15 21 27 33

686.19551835

Hint

Sample Explanation 1

Obviously, you can choose $5$ non-overlapping circles with radius $2$.

Subtasks

For $100\%$ of the testdata, $n,k\leq 10^5$, $r\leq 10^4$, $0\leq x_i\leq 10^9$.

This problem uses bundled tests. There are $7$ subtasks, and the score and constraints of each subtask are as follows:

Subtask $1$ ($11$ points): $k=n$.

Subtask $2$ ($13$ points): $n,k,r \leq 100$.

Subtask $3$ ($6$ points): $n,k \leq 1000$, $r\leq 20$.

Subtask $4$ ($15$ points): $n,k,r \leq 2000$, and the testdata are guaranteed to be randomly generated.

Subtask $5$ ($23$ points): $r\leq 20$.

Subtask $6$ ($12$ points): $k\leq 20$, $x_n \leq kr$.

Subtask $7$ ($20$ points): no special constraints.

Source

MtOI2019 Extra Round T5

Problem setter: disangan233

Problem reviewer: suwAKow, _sys

Translated by ChatGPT 5