ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC, Eastern subregion, Yekaterinburg, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Cheese

Time limit: 1.0 second
Memory limit: 64 MB
Plus il y a de fromage, plus il y a de trous
or plus il y a de trous, moins il y a de fromage
donc plus il y a de fromage, moins il y a de fromage
Paradoxe de l'emmental
Programmer Sasha went downhill skiing in the Swiss Alps this summer. Switzerland is famous for its banks and cheese. Sasha was not interested in banks, but he visited a cheese factory. He learned there that Swiss people treated cheese even more seriously than money. For example, they put cheese into vacuum packs in pieces of exactly 500 grams. If you think that it is very easy to cut off such pieces, then you are mistaken: there are holes in Swiss cheese, which must be taken into account. Fortunately, modern technologies make it possible to determine exactly the size and location of all cavities in a piece of cheese.
Cheese is fed to a cutting machine as a long bar of square section 10×10 cm and length 1 m. Assume that all cavities are spherical and do not intersect each other and the borders of the bar. The machine can cut the bar at right angle to the long edges using a micrometer scale (that is, a grid of size 1 μm). A special computer determines the value the coordinate along the long edge of the bar at which a cut should be made so that the weight of the next piece be exactly 500 grams. This value is rounded to micrometers and the machine cuts the bar. Then the computer determines where the next cut should be made, and so on, until the weight of the remaining piece is less than 500 grams. If it turns out that the last cut should be made at the coordinate of exactly 1 meter, then, of course, this cut is not made.
Write a program that determines the coordinates of the cuts exactly as the Swiss computer does.

Input

The first line contains the number n of cavities in a bar of cheese (0 ≤ n ≤ 100). The next n lines describe these cavities in the format xi yi zi ri, where (xi, yi, zi) are the coordinates of the center of a cavity and ri is its radius. The size of the bar is 10×100×10 along the x, y, and z axes, respectively. The coordinate origin is one of the corners of the bar; the unit of measure is 1 cm. It is known that 1 cm3 of Swiss cheese weighs 1 gram.

Output

Output the coordinates of the cuts on the scale of the cutting machine. In the first line output the number of cuts, and in the following lines give the coordinates of the cuts in micrometers measured from the beginning of the bar.

Sample

inputoutput
2
3.2 37.2 1.8 1
4.2 66.6 5.5 2.5
19
50000
100000
150000
200000
250000
300000
350000
400419
450419
500419
550419
600419
651114
706964
756964
806964
856964
906964
956964
Problem Author: Alexander Mironenko (prepared by Denis Musin)
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007
To submit the solution for this problem go to the Problem set: 1583. Cheese