题目描述

The aerobics class begins. The trainer says, "Please position yourselves on the training mat so that each one of you has enough space to move your arms around freely, and not hit anybody else." People start milling around on the mat, trying to position themselves properly. Minutes pass, and finally the trainer is so annoyed that he asks you to write a program that will position all the people correctly, hoping it will be quicker than letting them figure it out for themselves!

You are given the dimensions (width and length) of the mat on which the class takes place. For every student, there is a circular area she has to have for herself, with radius equal to the reach of her arms. These circles can not intersect, though they can touch; and the center of each circle (where the student stands) has to be on the mat. Note that the arms can reach outside the mat. You know that there's plenty of space on the mat — the area of the mat is at least five times larger than the total area of the circles required by all the people in the class. It will always be possible for all the people to position themselves as required.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of two lines. The first line contains three integers: $\mathbf{N}$, $\mathbf{W}$ and $\mathbf{L}$, denoting the number of students, the width of the mat, and the length of the mat, respectively. The second line contains $\mathbf{N}$ integers $\mathbf{r}_i$, denoting the reach of the arms of the $i^{th}$ student.

输出格式

For each test case, output one line containing "Case #$n$: $y$", where $n$ is the case number (starting from 1) and $y$ is a string containing $2\mathbf{N}$ numbers, each of which can be an integer or a real number: $\mathbf{x}_1$, $\mathbf{y}_1$, $\mathbf{x}_2$, $\mathbf{y}_2$, etc., where the pair $(\mathbf{x}_i, \mathbf{y}_i)$ is the position where the $i^{th}$ student should stand (with $0 \leq \mathbf{x}_i \leq \mathbf{W}$ and $0 \leq \mathbf{y}_i \leq \mathbf{L}$).

As there will likely be multiple ways to position the students on the mat, you may output any correct positioning; but remember that you may not submit an output file more than 200kB in size.

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

提示

Limits

• $1 \leq \mathbf{T} \leq 50$.
• $1 \leq \mathbf{W}, \mathbf{L} \leq 10^9$.
• $1 \leq \mathbf{r}_i \leq 10^5$.
• The area of the mat is at least 5 times larger than the total area of the circles:
• $5 \times \pi \times (\mathbf{r}_1^2 + \ldots + \mathbf{r}_\mathbf{N}^2) \leq \mathbf{W} \times \mathbf{L}$.

Test set 1 (6 Pts, Visible Verdict)

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

Test set 2 (15 Pts, Hidden Verdict)

• $1 \leq \mathbf{N} \leq 10^3$.
• The total number of circles in all test cases will be $\leq 6000$.