SPOJ "The Bulk" Hint

Basic Steps :

1. Remove faces non perpendicular to Z axis
2. Remove Unnecessary Points from all faces
3. Sort faces on the basis of height along Z axis
4. Assign sign to each face whether it contributes positive volumes or negative volume
5. Find Area of each face
6. volume contributed by each face = sign*height along Z axis*area
7. Answer is sum of volume contributed by each face.

1. Remove faces non perpendicular to Z axis

we need only faces which are perpendicular to a particular axis lets take it as z axis since if you know all faces of a cube perpendicular to z axis then you can predict the other faces so that is just an extra information.

2. Remove Unnecessary Points from all faces

If there are three points (x1,y,z),(x2,y,z) and (x3,y,z) given in order as shown in fig. then x2 is an unnecessary point removing that point will still result in the same line so remove such points. Similarly apply for y as shown in fig.

3. Sort faces on the basis of height along Z axis

Now to find empty cubes we need to decide the sign of faces . if the volume below some face is empty its sign is negative. Now to decide which face is below which face we have to short faces on the basis of there heights along z axis.

4. Assign sign to each face whether it contributes positive volumes or negative volume

Now to decide sign of a face its sign would be opposite to that of one above it. Since we have already sorted the faces start with the top face giving it a positive sign. Now for each face find a face above it which covers it or in other words overlaps it and give it a sign opposite to that face. Now to find such face for each face steps are
1. Among the points with highest Y value in a face find one with least x value let this                              point be (X,Y,Z).
2. Now for each face above it starting from the one just above it in terms of height with respect                to Z axis find the no of horizontal lines(parallel to x axis) passing through the  point(X,y,Z)                  such that y >= Y.
 3. If the count is odd it means the face is covering current face .
4. Give current face opposite sign of this face and move to next face

5. Find Area of each face

To find area of a face using co-ordinates (xi,yi) iterate over cordinates .Take the point (x1,y1) and next point (x2,y2) and add up to the answer (x1*y2 - y1*x2).do it for all the points and (sum/2) is the area of face.

6. volume contributed by each face = sign*height along Z axis*area

7. Answer is sum of volume contributed by each face.

To get the c++ code for reference request me for the same via my email prince.ranawat@gmail.com i will share link to my code with you.