找到包含所有矩形的最小区域
这是一个面试问题。
我们给出了各种矩形的尺寸，我们必须找出可以包围所有矩形的矩形区域（最小值）？ 矩形也可以旋转。
test case:- input: 3 //number of rectangles 8 8 4 3 3 4 output: 88 11x8: + - - - - - - + + - + | | | | | | | | | | + - + | | + - + | | | | | | | | + - - - - - - + + - + 在最小可能区域中拟合矩形之前，我查看了一个类似的问题
上述方法着眼于所有可能性，旋转，并确定所有布局情况下所有这些可能性的最小值。
我们不能建立一个算法，我们首先找到矩形区域的总和，然后寻找最大长度，宽度？
这个问题没有绝对的解决方案，但是有一些近似的解决方案，你可以在这里阅读其中的一些解决方案。
非方形基准上的最佳矩形包装 ：
给定一组矩形，我们的问题是找到包含它们的最小区域的所有包围矩形而不重叠。 我们将封闭的矩形称为边界框。 优化问题是NP难的 ，而决定一组矩形是否可以在给定的边界框中打包的问题是NP-complete ，通过从bin-packing减少（Korf 2003）。
最佳矩形填料的新改进 ：
Korf [2003]将矩形包装问题分为两个子问题：最小边界框问题和包含问题。 前者找到一个最小区域的边界框，可以包含一组给定的矩形，而后者则尝试将给定的矩形打包在给定的边界框中。 解决最小边界框问题的算法将解决包含问题的算法称为子例程。
最小边界框问题
解决最小边界框问题的一种简单方法是找到描述可行和可能最佳边界框集的最小和最大区域。 可以使用该范围内的区域生成所有维度的边界框，然后以非递减的面积顺序进行测试，直到找到所有可行的最小区域的解。 最小面积是给定矩形的面积之和。 最大区域由贪婪解决方案的边界框确定，该边界框通过将边界框高度设置为最高矩形的高度，然后在从左到右扫描时将矩形放置在第一个可用位置，并从每个列扫描从下到上。
另请参见最佳矩形填充：新结果 。
首先你应该检查一下，是否可以旋转或不旋转矩形？ 无论如何，你可以忽略“矩形”条件并解决点中的任务。 你有点数组（矩形的顶点）。 你的任务是找到最小面积的包围矩形。 如果无法旋转封闭的矩形，则解决方案是愚蠢的，并且具有复杂度O（n）。
生成矩形数组并制作点arrays，这些点是矩形的顶点。 接下来很简单：
long n; // Number of vertexes point arr[SIZE]; //Array of vertexes long minX = MAXNUMBER, minY = MAXNUMBER, maxX = -MAXNUMER, maxY = -MAXNUMBER; for (long i = 0; i < 4 * n; i++) { minX = MIN(minX, arr[i].x); minY = MIN(minY, arr[i].y); maxX = MIN(maxX, arr[i].x); maxY = MIN(maxY, arr[i].y); } long width = maxX - minX, height = maxY - minY; printf("%ddX%ld", width, height);
如果矩形可以旋转的另一个任务。 那你应该先：
- 构建矩形中所有点的最小凸多边形。 您可以使用任何现有的algorythms。 复杂度O（n log n）。 作为“格雷厄姆扫描”的例子： http ： //en.wikipedia.org/wiki/Graham%27s_scan
- 对凸多边形使用简单算法。 链接： http ： //cgm.cs.mcgill.ca/~orm/maer.html
在wiki中链接您的任务： http ： //en.wikipedia.org/wiki/Minimum_bounding_rectangle