给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。
图1 四个矩形的六个基本布局
4个矩形块中任一个矩形的边都与封闭矩形的边相平行，图1显示出了铺放4个矩形块的6种方案。这6种方案是唯一可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。
可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。
下面是一个分析，对每种布局有很清楚的解释：http://hi.baidu.com/readd123/item/f7c57925d963ab0872863e82
//下面的部分来自上述博客
只要找准几种状态就行了，题目中的6个已经足够了，举每个方块的选择顺序和放置方向就行了。
第4、5个在本质上其实是一样。如图，不同模式对应的最小面积如下：
设w1,w2,w3,w4表示4个方块的横长，h1,h2,h3,h4表示4个方块的纵长。w,h表示最小。
1：w=w1+w2+w3+w4；h=max(h1,h2,h3,h4)
2：w=max(w1+w2+w3,w4)；h=max(h1,h2,h3)+h4
3：w=max(w1+w2,w3)+w4；h=max(h1+h3,h2+h3,h4)
4：w=w1+w2+max(w3,w4)；h=max(h1,h3+h4,h2)
5：h=max(h1+h3,h2+h4)
对于w，我们细分为如下四种形式：
(1)：h3>=h2+h4；w=max(w1,w3+w2,w3+w4)
(2)：h3>h4 and h3<h2+h4；w=max(w1+w2,w2+w3,w3+w4) // 要理解这两条w是如何计算出来的。
(3)：h4>h3 and h4<h1+h3；w=max(w1+w2,w1+w4,w3+w4) //
(4)：h4>=h1+h3；w=max(w2,w1+w4,w3+w4)
*：h3=h4（图中没画）；w=max(w1+w2,w3+w4)
之后便是具体实现了：
/*
ID: wuqi9395@126.com
PROG: packrec
LANG: C++
*/
//http://hi.baidu.com/readd123/item/f7c57925d963ab0872863e82
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
struct node {
int x, y;
}e[10];
int mn = INF, h, w;
int next[10] = {0}, inx = 0;
node in[10], tmp, out[maxn];
bool cmp(node s, node v) {
return s.x < v.x;
}
void pack1() {
h = 0, w = 0;
for (int i = 0; i < 4; i++) {
h = max(h, in[i].y);
w += in[i].x;
}
tmp.x = min(w, h);
tmp.y = max(w, h);
if (w * h < mn) {
inx = 0;
out[inx++] = tmp;
mn = w * h;
}
else if (w * h == mn) {
out[inx++] = tmp;
}
}
void pack2() {
h = w = 0;
for (int i = 0; i < 3; i++) {
h = max(h, in[i].y);
w += in[i].x;
}
h += in[3].y;
w = max(w, in[3].x);
tmp.x = min(w, h);
tmp.y = max(w, h);
if (w * h < mn) {
inx = 0;
out[inx++] = tmp;
mn = w * h;
}
else if (w * h == mn) {
out[inx++] = tmp;
}
}
void pack3() {
h = w = 0;
h = max(max(in[0].y, in[1].y) + in[3].y, in[2].y);
w = max(in[0].x + in[1].x, in[3].x) + in[2].x;
tmp.x = min(w, h);
tmp.y = max(w, h);
if (w * h < mn) {
inx = 0;
out[inx++] = tmp;
mn = w * h;
}
else if (w * h == mn) {
out[inx++] = tmp;
}
}
void pack4() {
h = w = 0;
h = max(max(in[0].y + in[1].y, in[2].y), in[3].y);
w = max(in[0].x, in[1].x) + in[2].x + in[3].x;
tmp.x = min(w, h);
tmp.y = max(w, h);
if (w * h < mn) {
inx = 0;
out[inx++] = tmp;
mn = w * h;
}
else if (w * h == mn) {
out[inx++] = tmp;
}
}
void pack5() {
h = max(in[0].y + in[1].y, in[2].y + in[3].y);
if (in[1].y >= in[2].y + in[3].y) w = max(max(in[2].x, in[3].x) + in[1].x, in[0].x);
if (in[1].y > in[3].y && in[1].y < in[2].y + in[3].y) w = max(max(in[0].x + in[2].x, in[2].x + in[1].x), in[1].x + in[3].x); // 怎么改了这个就对了。。 之前是max(in[0].x, in[1].x) + max(in[2].x, in[3].x);
if (in[0].y + in[1].y >= in[3].y && in[1].y < in[3].y) w = max(max(in[0].x + in[2].x, in[0].x + in[3].x), in[1].x + in[3].x); //同上
if (in[0].y + in[1].y <= in[3].y) w = max(max(in[0].x, in[1].x) + in[3].x, in[2].x);
if (in[1].y == in[3].y) w = max(in[0].x + in[2].x, in[1].x + in[3].x);
tmp.x = min(w, h);
tmp.y = max(w, h);
if (w * h < mn) {
inx = 0;
out[inx++] = tmp;
mn = w * h;
}
else if (w * h == mn) {
out[inx++] = tmp;
}
}
int main ()
{
freopen ("packrec.in", "r", stdin);
freopen ("packrec.out", "w", stdout);
for (int i = 0; i < 4; i++) {
scanf("%d%d", &e[i].x, &e[i].y);
e[i + 4].x = e[i].y;
e[i + 4].y = e[i].x;
next[i] = i;
}
do {
int tot = 1 << 4;
for (int i = 0; i < tot; i++) {
for (int j = 0; j < 4; j++) {
if ((i >> j) & 1) in[j] = e[next[j]];
else in[j] = e[next[j] + 4];
}
pack1();
pack2();
pack3();
pack4();
pack5();
}
} while(next_permutation(next, next + 4));
cout<<mn<<endl;
sort(out, out + inx, cmp);
cout<<out[0].x<<" "<<out[0].y<<endl;
for (int i = 1; i < inx; i++) if (out[i].x != out[i - 1].x)
cout<<out[i].x<<" "<<out[i].y<<endl;
return 0;
}
[USACO Section 1.4] Packing Rectangles (模拟）
原文：http://blog.csdn.net/sio__five/article/details/19699283