fitting rectangles in the smallest possible area

Question

IOI 95

The six basic layouts of four rectangles

Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.

All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.

There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.

INPUT FORMAT
Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle's two sides. Each side of a rectangle is at least 1 and at most 50.

OUTPUT FORMAT
The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.

So this is the problem statement. I figured out that I want to try all 24*16 positions ( you can turn rectangle 90 degrees) against all these basic layouts and check the new area, however I have no idea how to implement this. Anything from some pseudo code to links to articles would help a lot. Thanks in advance.

Answer 1

While google does turn up some solutions, I guess some high level description will enable you to solve this on your own.

You can start by naming the rectangles in each of the 6 layout cases 1,2,3,4. Then you should be able to calculate the bounding box for each of the layouts for given instances of rectangles 1...4 (hint for the first case: width=sum of widths of 1...4, height=max of heigths of 1...4)

Then, as you said, you can try all possible combinations of naming four given rectangles with the indices 1...4 plus for each such possibility try out all possible rotations, and determine the minimum over all such possibilities in all layout cases.

Answer 2

Since there are only four rectangles, enumeration of all possible layouts should work. Of course really all possible layouts is too much, but we can merge equivalent layouts.

Let's consider only layouts where each rectangle cannot be moved left and up. This means that its upper border touches something and its left border touches something. All other layouts may be converted into such subset without making bounding box bigger.

When we choose the first rectangle (one of four), it can touch only left and top borders of bounding box, so we have only one possible position for its left-top vertex.

When we choose the second rectangle (one of three), its top border may touch either top border of the bounding box or bottom border of the first rectangle - 2 options. Similarly its left border may touch either left border of the bounding box or right border of the first rectangle - 2 more options. Thus we get 2x2=4 options for coordinate of its left-top vertex.

And so on for third and fourth rectangle.

Of course we should check at each step that there is no intersection between rectangles (e.g. if both of them will start from left-top corner of the bounding box). Also we sometimes will get obviously non-optimal layouts (e.g. when left-top vertex of the second rectangle coincides with right-bottom vertex of the first one), but that will not hurt result and can be removed if the solution is not fast enough.