在尽可能小的区域拟合矩形
IOI 95
四个矩形的六种基本布局
给出了四个矩形.找到最小的封闭(新)矩形,这四个矩形可以装入这些矩形而不重叠.最小的矩形是指面积最小的矩形.
所有四个矩形的边应平行于包围矩形的相应边.图1显示了将四个矩形组合在一起的六种方法.这六种是唯一可能的基本布局,因为任何其他布局都可以通过旋转或反射从基本布局中获得.在包装期间,矩形可以旋转90度.
可能存在满足要求的几个不同的封闭矩形,所有这些矩形都具有相同的面积.你必须生成所有这样的封闭矩形.
INPUT FORMAT
四行,每行包含两个正空格分隔的整数,表示矩形两边的长度.矩形的每一边至少为1,最多为50.输出格式
输出文件包含的行多于解决方案的数量.第一行包含一个整数:包围矩形的最小区域.以下每行包含由两个数字p和q描述的一个解,其中p <= q.这些行必须按p的升序排序,并且必须全部不同.
所以这就是问题陈述.我想我想尝试所有这些基本布局的所有24*16位置(你可以将矩形转90度)并检查新区域,但是我不知道如何实现它.从一些伪代码到文章链接的任何东西都会有很大帮助.提前致谢.
虽然谷歌确实提出了一些解决方案,但我想一些高级别的描述将使您能够自己解决这个问题.
您可以从6个布局情况1,2,3,4中的每一个中命名矩形开始.那么你应该能够为给定的矩形1 ... 4的实例计算每个布局的边界框(第一种情况的提示:宽度=宽度的总和为1 ... 4,高度=最大的高度为1 ... 4)
然后,如您所说,您可以尝试所有可能的组合,命名四个给定矩形,索引1 ... 4加上每个这样的可能性尝试所有可能的旋转,并确定所有布局情况下所有这些可能性的最小值.