P13073 [GCJ 2020 Finals] Musical Cords

Lauren 正尝试用竖琴演奏最美妙的音符。竖琴是一个半径为 $\mathbf{R}$ 厘米的圆形乐器。要演奏一个音符，必须在圆周上两个不同的固定点之间连接一根琴弦，并通过拨动琴弦发声。 圆周上共有 $\mathbf{N}$ 个固定点可用于连接琴弦。第 $i$ 个固定点的位置为从圆周最右侧点顺时针方向 $\mathbf{D}_i$ 纳度（1 纳度 = $10^{-9}$ 度）处。 不同固定点使用的固定技术不同。第 $i$ 个固定点需要消耗 $\mathbf{L}_i$ 厘米的琴弦用于固定。连接两个不同固定点 $i$ 和 $j$ 的琴弦总长度必须恰好为 $\mathbf{L}_i + \mathbf{L}_j + \text{distance}(i, j)$ 厘米。其中 $\text{distance}(i, j)$ 表示第 $i$ 个和第 $j$ 个固定点之间的几何弦长（即两点间的欧几里得距离）。 Lauren 认为琴弦越长，音符听起来越美妙。请问 Lauren 的竖琴可以使用的琴弦中，最长的 $\mathbf{K}$ 个长度分别是多少？

第一行输入测试用例数 $\mathbf{T}$。每个测试用例包含： 第一行三个整数 $\mathbf{N}$、$\mathbf{R}$ 和 $\mathbf{K}$：固定点数量、竖琴半径（厘米）和 Lauren 需要查询的琴弦长度数量。 接下来 $\mathbf{N}$ 行描述固定点，每行两个整数 $\mathbf{D}_i$ 和 $\mathbf{L}_i$，分别表示第 $i$ 个固定点的位置（纳度）和固定所需琴弦长度（厘米）。

对每个测试用例，输出一行 `Case #x: y1 y2 ... yK`，其中 $x$ 为测试用例编号（从 1 开始），$y_n$ 为所有 $\mathbf{N} \times (\mathbf{N}-1)/2$ 根可能琴弦的长度按非递增排序后的第 $n$ 个值。 每个 $y_n$ 允许存在绝对或相对误差不超过 $10^{-9}$。

**样例解释** 样例测试集 1 符合测试集 1 的限制条件。其他不符合该限制的样例可能出现在测试集 2 中。 注意：测试集 1 的样例中 $\mathbf{L}_i$ 值是为便于理解而设定的非随机值。您的解法必须通过这些样例。 在样例 #1 中，所有固定点的 $\mathbf{L}_i$ 值相同，因此应选择弦长最长的点对（即圆的水平直径，长度 4 厘米）。总长度为 $4 + 3 + 3 = 10$ 厘米。 在样例 #2 中，第四和第五个点非常接近第三个点，但 $\mathbf{L}$ 值较小。最优解来自前三个点的连接： - 第一和第二个点：长度 $10\sqrt{2} + 8 + 7 \approx 29.142136$ - 第一和第三个点：长度 $\approx 19.923894 + 8 + 9 \approx 36.923894$ - 第二和第三个点：长度 $\approx 12.855726 + 7 + 9 \approx 28.855726$ 因此选择第一和第三个点获得最大长度。 样例测试集 2：注意存在三组点对并列产生第 9 长的琴弦。不同琴弦可以交叉，因为 Lauren 每次只演奏一个音符。 **数据范围** - $1 \leq \mathbf{T} \leq 100$ - $\mathbf{N} = 150000$ 的用例不超过 10 个 - $5 \leq \mathbf{N} \leq 10^4$（当 $\mathbf{N} \neq 150000$ 时） - $1 \leq \mathbf{R} \leq 10^9$ - $0 \leq \mathbf{D}_1$ - $\mathbf{D}_i < \mathbf{D}_{i+1}$（对所有 $i$） - $\mathbf{D}_N < 360 \times 10^9$ **测试集 1（15 分，可见判定）** - $\mathbf{L}_i$ 在 1 到 $10^9$ 之间独立均匀随机生成 - $\mathbf{K} = 1$ **测试集 2（27 分，隐藏判定）** - $1 \leq \mathbf{L}_i \leq 10^9$（生成方式无限制） - $\mathbf{K} = 10$ 翻译由 DeepSeek V3 完成