Pack the balls in a box!

Problem code: DX

All submissions for this problem are available.

Suppose we have a set of balls and a large cuboid box, with a rectangle as its base. The box has a fixed size at the base, but we can choose its height. We would like to place all the balls within the box, and at the same time try to minimize its height.

Input

First, 2 integers, 10 a,b 100 - the dimensions of the rectangular base of the box. Then, an integer 1 n 10000, representing the number of balls. The following n values 1 ri 5 are the radii of the respective balls.

Output

You should write to output n triples of floating-point numbers, the ith triple being the x,y, and z coordinates of the center of the ith ball.

If we want to be precise, the coordinates of the points written to output must fulfill the following constraints for the i-th point: xi-ri 0, yi-ri 0, zi-ri 0, xi+ri a, yi+ri b. Moreover, for each i j, (xi - xj)2 + (yi - yj)2 + (zi - zj)2 (ri + rj)2 (no two balls are allowed to overlap).

Scoring

The goal is to minimize the height h of the box, where h = maxi (zi+ri). For each data set, your program will be scored by the proportion of the box volume actually used by the balls:

score = 4/3* *(r13+..+rn3)/(a*b*h).

The program is run independently for a number of data sets, and the displayed score is the mean of scores obtained for individual data sets.

Example

Input:
5 5
2
1.0
2.0

Output:
4.0 4.0 3.0
2.0 2.0 2.0

Score:
37.6991118/100.0 = 0.376991118

Author: admin
Date Added: 5-05-2009
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

pr0ton @ 2 Jun 2009 06:59 PM

From problem statement
"
Moreover, for each i ? j, (xi - xj)^2 (yi - yj)^2 ? (ri rj)2 (no two balls are allowed to overlap).
"

Shouldnt it be (xi - xj)^2 (yi - yj)^2 (zi-zj)^2 since it is 3D ?

I'm getting wrong answer, even though i'm doing something stupid like stacking balls on top of each other.

Thanks

admin 2 @ 2 Jun 2009 10:57 PM

Yes, you are right. This has been changed in the problem statement.

zhouerjin @ 6 Jun 2009 01:21 PM

it's too strange for this problem...
my algorithm is just greedy,then got correct answer
but if I sort the balls by their ri,and got WA..
I check my code and have test many testdata,and can't find any mistake...>.<
i want to know the judge how to check if the answer is correct,does it have some mistake?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions