P5617 [MtOI2019] Invisible Boundary Line

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

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.

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 one real number in one line, representing the required answer. It is guaranteed that the answer is less than $10^{14}$.

#### 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](https://www.luogu.org/contest/22840) T5 Problem setter: disangan233 Problem reviewer: suwAKow, _sys Translated by ChatGPT 5