IOI 95
四个矩形的六种基本布局
给出了四个矩形。找到最小的封闭(新)矩形,可以将这四个矩形安装到其中而不重叠。最小矩形是指面积最小的矩形。
所有四个矩形的边都应与封闭矩形的相应边平行。图 1 显示了将四个矩形拼接在一起的六种方法。这六种是唯一可能的基本布局,因为任何其他布局都可以通过旋转或反射从基本布局获得。矩形在包装过程中可以旋转 90 度。
可能存在几个不同的满足要求的封闭矩形,它们都具有相同的面积。您必须生成所有此类封闭矩形。
输入格式
四行,每行包含两个以空格分隔的正整数,表示矩形两条边的长度。矩形的每条边至少为 1,最多为 50。
输出格式
输出文件包含的行比解决方案的数量多。第一行包含一个整数:封闭矩形的最小面积。以下每一行都包含一个由两个数字 p 和 q 描述的解,其中 p
这就是问题陈述。我发现我想针对所有这些基本布局尝试所有 24*16 位置(您可以将矩形旋转 90 度)并检查新区域,但是我不知道如何实现这一点。从伪代码到文章链接的任何内容都会有很大帮助。提前致谢。
虽然谷歌确实找到了一些解决方案,但我想一些高级描述将使您能够自己解决这个问题。
您可以首先将 6 种布局情况中的每个矩形命名为 1、2、3、4。
然后,您应该能够计算矩形 1...4 给定实例的每个布局的边界框(第一种情况的提示:宽度 = 1...4 的宽度之和,高度 = 高度的最大值1...4)
然后,正如您所说,您可以尝试用索引 1...4 命名四个给定矩形的所有可能组合,并为每个此类可能性尝试所有可能的旋转,并确定所有布局情况下所有此类可能性的最小值。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)