Area K

You, and a group of other scientists, have recently discovered strange gravity anomalies on the planet Alderaan. Further analysis shows that the gravity anomalies are caused by some asteroids floating in orbit. The strange positioning of the asteroids notwithstanding, all scientists except you had decided that this is not a matter worthy of attention and departed to continue research on other places. On the other hand, you believe with pure heart that this is not merely a random event, and landed on the surface of Alderaan to continue your study.
After doing some scanning, you have recorded the positions of all asteroids on your navigation computer as points in a three-dimensional Cartesian system. Interestingly, the data shown by your scanning system indicates that there is some sort of force field around each asteroid – more precisely, the shape of every asteroid’s force field is a regular hexahedron whose every face is perpendicular to one of the axis of the coordinate system, which further confirmed your belief that there is something serious going on here. To find out the source of all these, you have decided to do a series of research on the planet.
The first research you have decided to conduct is to get the area of surface on the ground covered by exactly K asteroids’ force field. For simplicity, you can view the surface of Alderaan as the plane Z = 0.

There are multiple test cases in the input file. Each test case starts with one integer N (1 <= N <= 10⁴), the number of asteroids in orbit. Each of the next N lines consists of four integers X, Y, Z and L (-106<= X, Y <= 10⁶, 0 < Z, L <= 10⁶), describing the position of an asteroid and its edge length of the force field. The asteroid is just at the center of the hexahedron. The last part of each test case consists of one integer K (1 <= K <= N) followed by a blank line, meaning that you need to get the sum of areas on the ground affected by exactly K asteroids’ force fields.
There is a blank line between two successive test cases. A single line with N = 0 indicates the end of input file.

For each test case, output one real number on one separate line, the total area of surface covered by exactly K asteroids, in the format as indicated in the sample output.

2
1 0 1 2
0 1 1 2
1

0

Case 1: 6.000

2010 Asia Regional Tianjin Site —— Online Contest