Maximizing the Union Area of Selected Circles

Rikka has drawn n circles on the plane. The centers of the circles lie on the x‐axis, with the i-th circle centered at ( (x_i,0) ) ((x_i) are all distinct integers given in increasing order). All circles have the same radius (r). Instead of computing the sum of the areas of all (n) circles (which is too easy), Rikka asks you to choose exactly k circles (i.e. remove (n-k) circles) so that the area of the union of the selected circles is maximized.\n\nThe area of the union of circles is defined as the total area covered by at least one circle. Note that if two circles overlap their overlapping area is only counted once. In particular, if two circles do not intersect (i.e. the distance between their centers is at least (2r)), then the union area is simply the sum of their individual areas. Therefore, in the ideal case the maximum union area is (k\pi r^2) (when the chosen circles are pairwise disjoint). However, when some circles are too close so that (x_{i+1}-x_i<2r), they overlap and the effective union area decreases.\n\nFor two circles with centers separated by a distance (d (<2r)) the overlap area is given by [ I(d)=2r^2\arccos\left(\frac{d}{2r}\right)-\frac{d}{2}\sqrt{4r^2-d^2}.] Thus, if two circles overlap, the additional area contributed by the later circle (when “chained” to a previous one) can be thought of as (\pi r^2-I(d)). When the circles do not overlap (i.e. (d\ge2r)) the full area (\pi r^2) is contributed.\n\nA key observation is that when choosing k circles one may always choose the first and the last circle (i.e. with the minimum and maximum (x)–coordinate) so that the total spread (D = x_{n}-x_{1}) is as large as possible. In the ideal case we can have every two consecutive chosen circles disjoint, which happens when (D\ge2r(k-1)). In that case the maximal union area is (k\pi r^2). Otherwise, if (D < 2r(k-1)) the best strategy is to "spread out" the selected circles as evenly as possible so that the gap between consecutive chosen circles is (\Delta = \frac{x_n-x_1}{k-1}) (note that this value is less than (2r)) and each adjacent pair loses an area of (I(\Delta)) due to overlap. Hence the maximal union area is given by[ A_{max}=k\pi r^2-(k-1)\left[2r^2\arccos\left(\frac{\Delta}{2r}\right)-\frac{\Delta}{2}\sqrt{4r^2-\Delta^2}\right]. ] Note that when (\Delta\ge2r) the overlapping term becomes 0 and (A_{max}=k\pi r^2).\n\nYour task is to write a program that, given n, k, (r) and the sorted list of (x_i), computes the maximum union area of k circles. The answer is accepted if its relative error is less than (5\times10^{-8}).

inputFormat

The first line contains three numbers: (n), (k) and (r) (where (1\le k\le n\le10^5) and (r\le10^4)).\nThe second line contains (n) distinct integers (x_1, x_2, \dots, x_n) ((0\le x_i\le10^9)), given in increasing order.

outputFormat

Output a single number — the maximum possible union area of the selected k circles. The answer is accepted if its relative error is less than (5\times10^{-8}).

sample

3 2 1
0 100 101

6.283185307179586