P13073 [GCJ 2020 Finals] Musical Cords

Lauren is trying to play the most beautiful notes possible using a harp. The harp is a circle with a radius of $\mathbf{R}$ centimeters. To play a note, a cord must be attached to the harp in a way that connects two different attachment points on the perimeter of the circle. Lauren then plucks this cord to play a note. There are $\mathbf{N}$ attachment points on the perimeter of the circular harp at which a cord can be attached. The $i$-th such attachment point is at a location that is $\mathbf{D}_i$ nanodegrees (a nanodegree is $10^{-9}$ degrees) clockwise around the perimeter of the circular harp, starting from the rightmost point on the perimeter. Not all attachment points use the same technology to properly fix the cords onto them. The $i$-th attachment point requires $\mathbf{L}_i$ centimeters of cord to be used for attaching. A cord fixed between two different attachment points $i$ and $j$ needs to be exactly $\mathbf{L}_i + \mathbf{L}_j + \text{distance}(i, j)$ centimeters long. By $\text{distance}(i, j)$ we mean the length of the geometric chord connecting the $i$-th and $j$-th attachment points, that is, the Euclidean distance between the two points. Lauren thinks that notes sound better when they come from longer cords. What are the $\mathbf{K}$ longest cords that can be used with Lauren's harp?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of a test case contains three integers: $\mathbf{N}$, $\mathbf{R}$ and $\mathbf{K}$: the number of attachment points, the radius of the circular harp in centimeters, and the number of lengths of cords that Lauren is interested in knowing. The next $\mathbf{N}$ lines describe the attachment points. The $i$-th of these lines contains two integers, $\mathbf{D}_i$ and $\mathbf{L}_i$, which describe the position (in number of nanodegrees clockwise from the rightmost point of the harp) and length of cord in centimeters needed at the $i$-th attachment point.

For each test case, output one line containing Case #x: $y_1$ $y_2$ ... $y_{\mathbf{K}}$, where $x$ is the test case number (starting from 1), and $y_n$ is the $n$-th value in the list of lengths of all $\mathbf{N} \times (\mathbf{N}-1)/2$ cords that can be used in Lauren's harp, sorted in non-increasing order. Each $y_n$ will be considered correct if it is within an absolute or relative error of $10^{-9}$ of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

**Sample Explanation** Sample Test Set 1 meet the limits for Test Set 1. Another sample case that does not meet those limits could appear in Test Set 2. Note: the $\mathbf{L}_i$ values in these sample cases for Test Set 1 were chosen for ease of understanding and were not randomly generated. Your solution will be run against these sample cases and must pass them. In Sample Case #1, all of the attachment points have the same value, so we should pick the pair connected by the longest chord, which in this case is a horizontal diameter of the circle that has a length of 4 centimeters. So the total length needed is $4 + 3 + 3 = 10$ centimeters. In Sample Case #2, the fourth and fifth points are extremely close to the third point, but have much smaller $\mathbf{L}$ values. We can effectively rule them out and focus on the possible connections among the first three points, as follows: - first and second points: length $10\sqrt{2} + 8 + 7 \approx 29.142136$. - first and third points: length $\approx 19.923894 + 8 + 9 \approx 36.923894$. - second and third points: length $\approx 12.855726 + 7 + 9 \approx 28.855726$. Using the first and third points gives us the greatest total length. Sample Test Set 2: Notice that there are three possible pairs of points tied for producing the 9th longest cord. Also, it is fine if lines connecting different pairs of points intersect, since Lauren will only be playing one note at a time. **Limits** - $1 \leq \mathbf{T} \leq 100$. - $\mathbf{N} = 150000$ in at most 10 cases. - $5 \leq \mathbf{N} \leq 10^4$ in all cases with $\mathbf{N} \neq 150000$. - $1 \leq \mathbf{R} \leq 10^9$. - $0 \leq \mathbf{D}_1$. - $\mathbf{D}_i < \mathbf{D}_{i+1}$, for all $i$. - $\mathbf{D}_N < 360 \times 10^9$. **Test Set 1 (15 Pts, Visible Verdict)** - $\mathbf{L}_i$ is chosen independently and uniformly at random between 1 and $10^9$, inclusive, for each $i$. - $\mathbf{K} = 1$. **Test Set 2 (27 Pts, Hidden Verdict)** - $1 \leq \mathbf{L}_i \leq 10^9$, for all $i$. - (There is no guarantee as to how each $\mathbf{L}_i$ is generated.) - $\mathbf{K} = 10$.