Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task 1-1: Packing Rectangles
发信站: 哈工大紫丁香 (2002年03月29日13:28:36 星期五), 站内信件

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 si
des of the enclosing rectangle. Figure 1 shows six ways to fit four rectangl
es 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 requir
ements, all with the same area. You have to produce all such enclosing recta
ngles.
　
Input Data
The input file INPUT.TXT consists of four lines. Each line describes one giv
en rectangle by two positive integers: the lengths of the sides of the recta
ngle. Each side of a rectangle is at least 1 and at most 50.
Output Data
The output file OUTPUT.TXT should contain one line more than the number of s
olutions. The first line contains a single integer: the minimum area of the 
enclosing rectangles (Subtask A). Each of the following lines contains one s
olution 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.
_____________     ______________
| INPUT.TXT |     | OUTPUT.TXT |
|___________|     |____________|
| 1 2       |     | 40         |
| 2 3       |     | 4 10       |
| 3 4       |     | 5 8        |
| 4 5       |     |____________|
|___________|
Figure 2: Example input and output

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]