Problem Background

"Explode, reality! Shatter, synapses! Banishment... this world!"

Problem Description

Rikka firmly believes that her father is waiting for her in the "Invisible Boundary Line." In Rikka's dream, the "Invisible Boundary Line" appeared, which is a pattern composed of $n$ circles.

Specifically, there is a Cartesian coordinate system with $n$ points on the $x$-axis, where the $i$-th point has coordinates $(x_i, 0)$.

Rikka drew $n$ circles with each point as the center and a radius of $r$. Initially, she wanted you to help her calculate the total area of these $n$ circles, but this problem was too simple.

After some thought, Rikka wants you to calculate the maximum total area of $k$ circles (i.e., removing $n-k$ circles) after selection.

For all data, $n, k \leq 10^5$, $r \leq 10^4$, $0 \leq x_i \leq 10^9$, $x_i$ are integers and distinct. The input $x_i$ is guaranteed to be in monotonically increasing order.

Since the answer is too large, Rikka considers that your computer may not be able to maintain high precision, so as long as your answer has a relative error less than $5 \times 10^{-8}$ from the standard answer, your answer is considered correct.

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

Input Format

There are $2$ lines in total.

The first line inputs $3$ integers $n$, $k$, and $r$.

The second line inputs $n$ integers $x_1 \ldots x_n$.

Output Format

One line with $1$ real number, representing the answer, which is guaranteed to be less than $10^{14}$.

Sample Input and Output

Sample Input #1

8 5 2
1 3 7 11 15 21 27 33

Sample Output #1

62.83185307

Sample Input #2

8 5 8
1 3 7 11 15 21 27 33

Sample Output #2

686.19551835

Notes

Sample Explanation 1

Clearly, it is possible to select $5$ non-overlapping circles with a radius of $2$.

Subtasks

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

This problem uses bundled testing with a total of $7$ subtasks, each with its own score and constraints:

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$, data is guaranteed to be randomly generated.

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

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

Subtask $7$ ($20$ points): No special restrictions.

Problem Source

MtOI2019 Extra Round T5

Problem Author: disangan233

Problem Tester: suwAKow, _sys

见题面 Input 部分

见题面 Output 部分