algorithm - 在尽可能小的区域内拟合矩形

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.

这就是问题陈述。我发现我想针对所有这些基本布局尝试所有 24*16 位置(您可以将矩形旋转 90 度)并检查新区域，但是我不知道如何实现它。从一些伪代码到文章链接的任何内容都会有很大帮助。提前致谢。

Answer 1

虽然谷歌确实提供了一些解决方案，但我想一些高级描述可以让您自己解决这个问题。

您可以首先命名 6 种布局案例中的矩形 1、2、3、4。然后，您应该能够为矩形 1...4 的给定实例计算每个布局的边界框(第一种情况的提示:宽度 = 1...4 的宽度之和，高度 = 的最大高度1...4)

然后，正如您所说，您可以尝试所有可能的组合，命名四个给定的矩形，索引为 1...4 加上每个这样的可能性，尝试所有可能的旋转，并确定所有布局中所有这些可能性的最小值例。