Changed it to 24. Still it's not big enough

So now you have two sets of segments. Note each set has O(N) segments. We want to find all points of interest, basically, the points which can be present on our upper hull. For that, create a set of points S. Add each vertex belonging to at least one of the segments to S. Now for all segments, if they intersect, add their intersection points to S as well.

Now create another set Y from S such that Y stores the y coordinate of every point in S. Now our target is for all , find the maximum x that it stretches to. To do that, let's fix the y coordinate, say it is r. Now iterate over all segments, and if the segment is such that it intersects the line y = r, then evaluate the line (assume the segment is a line) by fixing the y coordinate in that line as r, and finding the corresponding x coordinate. Find the maximum such x coordinate for every y.

Now iterate over all in increasing/decreasing order, and use the formula for volume of a frustum of a cone. The radii for the frustum will be the maximum value of x coordinate for the current y value, and the maximum value of x coordinate for the previous y value. Height will be the difference in the current y coordinate and the previous one.

AC Code: ideone

Edit: When you are iterating over all points P, don't add (x, P.y) for every line L. Rather add it for only that line L' such that the corresponding x is maximum

Edit 2: Rewrote Explanation.

This is a greedy approach.

Let's cut off slices of thickness exactly S (it doesn't make sense to cut off thicker slices). If the total volume of the slices cut is the same, their total area is also the same regardless of the order in which the cuts are done. We can keep cutting them off until a piece with all dimensions less than 2S is left. The dimensions of this piece are given as dim.

int[] dim = new int[] {A % S + S, B % S + S, C % S + S};

This last piece is also a good slice, with thickness equal to the smallest of its dimensions and area equal to the product of two other dimensions. To make it a slice of thickness S, we can make a cut in the smallest dimension (this preserves the area of the slice). To get the dimensions of the throwaway piece (from which we can't produce any more slices), we model this cut:

Arrays.sort(dim);
dim[0] -= S;

Finally, the only part of the original piece that is not converted to slices of thickness exactly S is this throwaway piece. To find the total area of good slices, we take the used volume (the volume of original piece minus the volume of throwaway piece), and divide it by S.

return (A * B * C - dim[0] * dim[1] * dim[2]) / S;

It's complexity is O(n^4). Declare a global cnt variable, increment it before if(ret != -1) return ret; you can see that there 2.97*10^8 recursive calls. I also had same solution but couldn't submit because of one typo error but it failed in practice room afterwards.

Most people used O(n^3) solution. Instead of loop, you can cut two blocks one with size s and other size side-s. How to prove this is optimal?

And there is O(1) solution.

I tested my solution which is almost identical to yours, with complexity O(n⁴).