David is a well-known Magician for crossing concrete walls of buildings during his shows. However, he is losing his ability every time he has to go through large concrete walls. To overcome this problem, David is now retrieving satellite data of the building before going into action. This data consists of a three-dimensional description of the building concrete structure. He uses this information to find the set of walls that minimize the amount of concrete to go through in a straight line. You should write an algorithm that helps David to choose the right walls to cross. Obviously, the algorithm should provide the answer on-the-fly, even for sky-wrappers with thousands of floors...
Given a set of three-dimensional orthogonal boxes (the walls), choose a non-empty subset such that the sum of the width of the chosen boxes, measured in a horizontal line segment (i.e. parallel to the x-coordinate), is minimized.
The building has several floors. There may be several overlapping boxes in each floor. In this case, the width of the overlapping should be subtracted from the total width of the overlapped boxes. For instance, given two boxes, A and B, with width(A) = 10, width(B) = 15, and width(A ∩ B) = 5, then width(A ∪ B) = 20 (10 + 15 - 5).
Important Note: David is only allowed to cross at fixed half-integer y-coordinate values (that is, 0.5, 1.5, 2.5, ...) and within the limits of each floor.
Each test file starts with the number of boxes, followed by the location of each box, with the following sintaxe: <min x> <min y> <max x> <max y> <min floor> <height>.
The numbers min x and min y are the minimal x- and y-coordinates of the box in the bidimensional plane, while max x and max y are the maximal x- and y-coordinates. The number min floor is the floor number where the base of the box is located. The number <height> is the height of the box in terms of number of floors. Note that a <height> equals to zero means that the box is located in a single floor. The coordinates are nonnegative integers. Do not expect any kind of structure on the location of boxes in the building.
Total width of the chosen boxes (minus the width of the overlapping).
9 0 5 3 8 0 1 2 4 6 8 0 0 6 3 8 7 0 1 1 1 2 5 0 1 7 0 8 3 0 0 0 0 7 1 0 0 3 7 7 8 1 0 0 0 6 4 1 0 4 4 5 6 1 0
2
Note: See the solution for the test above in Figure 1. The dashed arrow indicates the direction that David should follow.
Figure 1: Ground floor (left plot) and first floor (right plot).