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.
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 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
3.2 37.2 1.8 1
4.2 66.6 5.5 2.5
Problem Author: Alexander Mironenko (prepared by Denis Musin)
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007