Description

有氧操课程开始了。教练说：“请大家在训练垫上站好，保证每个人都有足够的空间能自由挥动手臂，而且不会碰到其他人。”大家开始在垫子上走动，试图找到合适的位置。时间一分一秒过去，最终教练非常恼火，要求你写一个程序来给所有人安排正确的位置，希望这样比让他们自己慢慢挪要快！

你会得到课程所用垫子的尺寸（宽度和长度）。对于每位学员，都有一个属于她自己的圆形区域，半径等于她手臂的可达范围。这些圆不能相交，但可以相切；每个圆的圆心（即学员所站的位置）必须在垫子上。注意，手臂可以伸出垫子之外。你知道垫子的空间非常充足——垫子的面积至少是所有圆面积总和的五倍。所有学员都能按要求站下这一点始终成立。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据包含两行。第一行三个整数：$\mathbf{N}$、$\mathbf{W}$ 和 $\mathbf{L}$，分别表示学员人数、垫子的宽度和长度。第二行包含 $\mathbf{N}$ 个整数 $\mathbf{r}_i$，表示第 $i$ 位学员的手臂可达半径。

Output Format

对于每个测试用例，输出一行 "Case #$n$: $y$"，其中 $n$ 为测试用例编号（从 1 开始），$y$ 是一个包含 $2\mathbf{N}$ 个数字的字符串，每个数字可以是整数或实数：$\mathbf{x}_1$、$\mathbf{y}_1$、$\mathbf{x}_2$、$\mathbf{y}_2$，依此类推，其中 $(\mathbf{x}_i, \mathbf{y}_i)$ 表示第 $i$ 位学员应站的位置（$0 \leq \mathbf{x}_i \leq \mathbf{W}$ 且 $0 \leq \mathbf{y}_i \leq \mathbf{L}$）。

由于学员在垫子上的站位方案可能有多种，你可以输出任意一个合法方案；但请注意，提交的输出文件不得超过 200kB。

2
2 6 6
1 1
3 320 2
4 3 2

Case #1: 0.0 0.0 6.0 6.0
Case #2: 0.0 0.0 7.0 0.0 12.0 0.0

Hint

限制条件

• $1 \leq \mathbf{T} \leq 50$
• $1 \leq \mathbf{W}, \mathbf{L} \leq 10^9$
• $1 \leq \mathbf{r}_i \leq 10^5$
• 垫子的面积至少是所有圆面积总和的 5 倍：
• $5 \times \pi \times (\mathbf{r}_1^2 + \ldots + \mathbf{r}_\mathbf{N}^2) \leq \mathbf{W} \times \mathbf{L}$

测试集 1（6 分，结果可见）

• $1 \leq \mathbf{N} \leq 10$

测试集 2（15 分，结果隐藏）

• $1 \leq \mathbf{N} \leq 10^3$
• 所有测试用例的圆总数不超过 6000

翻译由 ChatGPT-4.1 完成。