시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB45131126.829%

문제

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, T.  T test cases follow. Each test case consists of two lines. The first line contains three integers: NW 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.

Limits

  • 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.
  • 1 ≤ N ≤ 103.
  • The total number of circles in all test cases will be ≤ 6000.

출력

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: x1y1x2y2, etc., where the pair (xiyi) is the position where the ithstudent should stand (with 0 ≤ xi ≤ W 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.

예제 입력 1

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

예제 출력 1

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

출처

Contest > Google > Code Jam > Google Code Jam 2012 > Round 2 B2번

채점 및 기타 정보

  • 예제는 채점하지 않는다.