Task 1-1: Packing Rectangles
Figure 1: 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.
There may exist several different enclosing rectangles fulfilling the
requirements, all with the same area. You have to produce all such
enclosing rectangles.
Input Data
The input file INPUT.TXT consists of four lines.Each line describes one given rectangle by two positive integers: the lengths of
the sides of the rectangle. Each side of a rectangle is at least 1 and at most
50.
Output Data
The output file OUTPUT.TXT should contain one linemore than the number of solutions. The first line contains a single integer: the
minimum area of the enclosing rectangles (Subtask A). Each of the following
lines contains one solution described by two numbers p and q with
p<=q (Subtask B). These lines must be sorted in ascending order
of p, and must all be different.
Example Input and Output
Figure 2 gives example input and output files._____________ ______________Figure 2: Example input and output
| INPUT.TXT | | OUTPUT.TXT |
|___________| |____________|
| 1 2 | | 40 |
| 2 3 | | 4 10 |
| 3 4 | | 5 8 |
| 4 5 | |____________|
|___________|