QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 1024 MB Total points: 21

# 5894. Aerobics

Statistics

Problem

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.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line contains three integers: N, W and L, denoting the number of students, the width of the mat, and the length of the mat, respectively. The second line contains N integers ri, denoting the reach of the arms of the ith student.

Output

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 2N numbers, each of which can be an integer or a real number: x1, y1, x2, y2, etc., where the pair (xi, yi) is the position where the ith student should stand (with 0 ≤ xiW and 0 ≤ yi ≤ 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.

Limits

Memory limit: 1GB.

Time limit: 40 8 seconds per test set.

1 ≤ T ≤ 50.

1 ≤ W, L ≤ 109.

1 ≤ ri ≤ 105.

The area of the mat is at least 5 times larger than the total area of the circles: 5π(r12 + ... + rN2) ≤ W*L.

Test set 1 (Visible Verdict; 6 Points)

1 ≤ N ≤ 10.

Test set 2 (Hidden Verdict; 15 Points)

1 ≤ N ≤ 103.

The total number of circles in all test cases will be ≤ 6000.

Sample

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