在最小可能的区域内放置矩形

Question

IOI 95 给定四个矩形，请找到最小的包含它们的矩形，使得它们不重叠。最小矩形是指面积最小的矩形。

所有四个矩形的边应该平行于外接矩形的相应边。图1显示了4个矩形组合成6种基本布局的方式。这6种是唯一可能的基本布局，因为任何其他布局都可以通过旋转或镜像从基本布局获得。在打包过程中，矩形可以旋转90度。

可能存在多个不同的满足要求的外接矩形，其面积相同。您必须产生所有这样的外接矩形。 输入格式
四行，每行包含两个正整数，表示矩形的两个边的长度。每个矩形的边长至少为1且最多为50。 输出格式
输出文件比解决方案的数量多一个线。第一行包含一个整数：外接矩形的最小面积。以下每行包含一种由两个数字p和q描述的解决方案，其中p≤q。这些行必须按p升序排序，并且必须各不相同。

这是问题陈述。我想尝试对所有24*16个位置（您可以旋转矩形90度）与所有这些基本布局进行检查，并检查新区域，但我不知道如何实施。任何东西，从伪代码到文章链接都会非常有帮助。谢谢。

- Marijus

---

事实上，我还在上高中，他们现在正在教循环。 - Marijus

忽略了IOI的评论，抱歉。 - Doc Brown

尝试在Google上搜索“约束二维切割算法”。我不确定是否真的只有24 * 16种组合。（虽然你的问题并不完全是经典的切割问题，其中库存通常是固定的） - Guy Sirton

排列数量：4!，旋转数量：2^4 - dcn

我不知道你是否可以在这里仅使用线性排列。例如，看看你的右侧图表：如果右上角的块稍微小一些，你就可以将其挤入其他两个块之间的空隙中。也就是说，我认为线性顺序和二维排列之间不存在一对一的映射关系。 - Guy Sirton

相关：找到包含所有矩形的最小区域 - jfs

Answer 1

虽然谷歌可以找到一些解决方案，但我认为提供一些高级描述将使您能够自行解决此问题。

您可以从为每个6种布局情况中的矩形命名为1、2、3、4开始。然后，您应该能够计算出给定矩形1…4实例的每个布局的边界框（对于第一种情况的提示：宽度= 1…4宽度之和，高度= 1…4高度之间的最大值）。

接下来，如您所说，您可以尝试使用索引1…4为四个给定矩形命名的所有可能组合，并针对每种可能性尝试所有可能的旋转，并在所有布局情况下确定所有这些可能性的最小值。

- dcn

Answer 2

由于只有四个矩形，枚举所有可能的布局应该可行。当然，真正的所有可能性太多了，但我们可以合并等效的布局。

让我们只考虑每个矩形不能向左和向上移动的布局。这意味着它的上边界接触到某物，它的左边界接触到某物。所有其他布局都可以转换为这种子集，而不会使边界框变大。

当我们选择第一个矩形（四个之一）时，它只能接触到边界框的左侧和顶部边界，因此我们只有一个可能的左上顶点位置。

当我们选择第二个矩形（三个之一）时，它的上边界可以接触边界框的顶部边界或第一个矩形的底部边界-2个选项。类似地，它的左边界可以接触边界框的左边界或第一个矩形的右边界-又有2个选项。因此，我们得到了4个选项作为其左上顶点的坐标。

对于第三个和第四个矩形也是如此。

当然，在每个步骤中，我们应该检查矩形之间是否存在交集（例如，如果它们都从边界框的左上角开始）。此外，有时我们会得到明显非最优的布局（例如，当第二个矩形的左上顶点与第一个矩形的右下顶点重合时），但这不会影响结果，并且如果解决方案不够快，则可以将其删除。

- maxim1000

Answer 3

基本上，给定矩形的所有24 * 16组合都可以通过考虑反射和旋转以及矩形的排列组合从上面显示的6个图表中派生出来。

- vivek