找到包含所有矩形的最小区域
这是一个面试问题。
我们给出了各种矩形的尺寸，我们必须找出可以包含所有矩形的矩形区域（最小）？ 矩形也可以旋转。
test case:-
input:
3 //number of rectangles
8 8
4 3
3 4
output:
88
11x8:
+ - - - - - - + + - +
| | | |
| | | |
| | + - +
| | + - +
| | | |
| | | |
+ - - - - - - + + - +
我在最小的可能区域中查看类似的问题，然后再安装矩形
上述方法着眼于所有布局情况下的所有可能性，旋转并确定所有这些可能性的最小值。
我们不能建立一个算法，我们首先找到矩形区域的总和，然后查找最大长度，宽度？
这个问题没有绝对的解决方法，但有几个近似的解决方案，你可以在这里阅读其中的一些。
非正方形基准上的最佳矩形包装：
给定一组矩形，我们的问题是找到所有包含最小区域的矩形，它们不会重叠。 我们将一个封闭矩形称为边界框。 优化问题是NP难题 ，而决定一组矩形是否可以打包在一个给定的边界框中的问题是NP完全的 ，通过减少装箱（Korf 2003）。
最佳矩形包装的新改进：
Korf [2003]将矩形打包问题分为两个子问题：最小边界框问题和遏制问题。 前者找到可包含给定矩形集的最小区域边界框，而后者尝试将给定矩形包装在给定边界框中。 解决最小边界框问题的算法将解决遏制问题的算法称为子程序。
最小包围盒问题
解决最小边界框问题的一个简单方法是找到描述可行和潜在最优边界框集合的最小和最大区域。 可以在这个范围内的区域内生成所有维度的边界框，然后以非递减的区域顺序进行测试，直到找到所有可行的最小面积解决方案。 最小面积是给定矩形区域的总和。 最大面积取决于通过将边界框高度设置为最高矩形边界的贪心解决方案的边界框，然后在从左到右扫描时将矩形放置在第一个可用位置，并且从每个列扫描从下到上。
另请参阅最佳矩形包装：新结果。
首先你应该检查，可能是围绕矩形旋转或不旋转？ 无论如何，你可以忽略“矩形”条件，并以点数解决任务。 你有点阵列（它们是矩形的顶点）。 你的任务是找到最小面积的包装矩形。 如果封闭的矩形不能旋转，那么解决方案很愚蠢并且复杂度为O（n）。
生成矩形数组并创建点矩阵的顶点。 接下来很简单：
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);
如果矩形可以旋转，另一个任务。 那么你应该先：
在wiki中链接您的任务：http://en.wikipedia.org/wiki/Minimum_bounding_rectangle
链接地址: http://www.djcxy.com/p/63233.html