在尽可能小的区域拟合矩形 [英] fitting rectangles in the smallest possible area
问题描述
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.
所有四个矩形应该有它们的侧面平行于包围矩形的相应两侧。图1显示了六种方法，以适应四个矩形在一起。这六个是唯一可能的基本布局，因为任何其它的布局可以从一个基本的布局通过旋转或反射而获得。在填充期间矩形可以旋转90度。
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.
输入格式
四大行，即重新present矩形的两边的长度各包含两个正空格隔开的整数。一个矩形的每一侧为至少1且至多50
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.
输出格式
输出文件包含比解决方案的头号行了。第一行包含一个整数：包围矩形的最小面积。每个以下的行的含有由两个数p和q与对中所述一个解决方案; = Q。这些行必须按升序的p进行排序，并且必须是不同的。
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度），对所有这些基本的布局，并检查了新的领域，但我不知道如何实现这一点。任何东西，从一些伪code到文章的链接将有很大的帮助。先谢谢了。
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.
推荐答案
虽然谷歌确实把一些解决方案，我想一些高层次的描述将使您能够解决这个你自己了。
While google does turn up some solutions, I guess some high level description will enable you to solve this on your own.
您可以通过命名矩形在每个6布局例1,2,3,4启动。 然后，你应该能够计算出边界框每个布局为长方形1给出实例... 4（提示对于第一种情况：宽度为1 ... 4，高度=最大的heigths的宽度= SUM 1 ... 4）
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)
然后，就像你说的，你可以尝试一下，任命四个给定的矩形与指数的所有可能的组合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.
这篇关于在尽可能小的区域拟合矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
