P5762 [NOI1997] Satellite Coverage

SERCOI (Space-Earth Resource Cover-Observe Institute) is an organization dedicated to using satellite technology to observe and cover space and Earth resources. They have successfully developed a new type of resource-observation satellite, SERCOI-308. This satellite can cover a cube-shaped region of a certain size in a 3D Cartesian coordinate system, with the satellite located at the center of the cube. Here, $(x,y,z)$ is the coordinate of the cube’s center point, and $r$ is the distance from the center to each face of the cube (that is, $r$ is half of the cube’s height). All edges of the cube are parallel to the corresponding coordinate axes. We can use a 4-tuple $(x,y,z,r)$ to describe the state of a satellite, and the volume of space it can cover. Since the volume that a single satellite can cover is limited, there may be several satellites working together in space. The regions they cover may overlap, as shown in the figure below (the shaded part indicates the overlapping region).  Write a program that, given the distribution of the satellites, computes the total volume covered by all of them.

The first line contains a positive integer $N$ ($1 \le N \le 100$), which represents the total number of satellites in space. The next $N$ lines each give the state of one satellite: four positive integers $x,y,z,r$ separated by spaces, representing the coordinates of the center of the cube it can cover and its half-height. Here, $-1000 \le x,y,z \le 1000$ and $1 \le r \le 200$.

Only one line, containing a positive integer, which represents the total volume of space covered by all these satellites.

Translated by ChatGPT 5