这是一个面试问题。
给出各种矩形的尺寸，我们需要找到能够包裹它们所有的矩形的最小面积？ 矩形也可以旋转。
test case:-
input:
3 //number of rectangles
8 8
4 3
3 4
output:
88
11x8:
+ - - - - - - + + - +
| | | |
| | | |
| | + - +
| | + - +
| | | |
| | | |
+ - - - - - - + + - +
这个问题没有绝对的解决方案，但有几种近似的解决方案，你可以在这里阅读一些相关内容。
给定一组矩形，我们的问题是找到所有包含它们且不重叠的最小面积外接矩形。我们称之为边界框。优化问题是NP-hard，而判断一组矩形能否在给定的边界框中放置是NP-complete问题，通过从bin-packing(Korf 2003)中减少实现。
Korf [2003] 将矩形装箱问题分为两个子问题：最小外接矩形问题和包含问题。前者查找能够包含给定矩形集的最小面积边界框，而后者尝试将给定的矩形放入给定的边界框中。解决最小外接矩形问题的算法将调用解决包含问题的算法作为一个子程序
解决最小外接矩形问题的一种简单方法是找到描述可行且可能最优边界框集合的最小和最大面积。可以生成所有维度的边界框，其面积在此范围内，并按非递减顺序进行测试，直到找到最小面积的所有可行解为止。最小面积是给定矩形的面积之和。最大面积由贪心算法找到的边界框决定，将边界框高度设置为最高矩形的高度，然后从左到右扫描时在第一个可用位置放置矩形，并对于每一列从下到上进行扫描。
另请参阅最优矩形装箱：新结果.
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);
如果矩形可以旋转，则您需要首先执行以下操作：
您在维基百科上的任务链接：http://en.wikipedia.org/wiki/Minimum_bounding_rectangle