前言：
这是一道令人望而却步的题，没有什么技术难度却又很需要勇气。解决它所需要花费的时间实际并不长，但就是怕麻烦的这种心理障碍让我迟迟无法下手，真需要好好反省一下。
题目大意：
给出4个矩形的长宽，求能包含4个矩形的最小矩形的面积，并输出其长宽。
思路：
题目通过图片形式给出了6种基本组合方式（4、5其实是一种），只需要把4个矩形插入相应位置即可。通过全排列遍历所有插入方案，再通过四重循环遍历所有翻转方案（横放或竖放）。简单计算下：需要遍历一共5*4!*2^4个方案后才能确定最终答案。
代码：
/*
ID: lujunda1
LANG: C++
PROG: packrec
*/
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
int rect[4][2];
//rectangle 用于存储4个矩形的长宽，rect[i][0]表示第i个矩形的长度，rect[i][1]表示其宽度。
int order[4]={0,1,2,3};
//顺序数组，每个基本排列中，交换矩形的位置。共有24种组合。
int tmp[4][2];
//存储通过顺序处理和翻转处理后的矩形信息。
int t[4];
//t[i]为1时，表示第i个矩形需要翻转90°，为0时不需要翻转。
int min_size=1000000;
//表示最小面积 。
int total;
//表示最小面积包含的方案数量。
map<int,bool> mark;
struct result
{
int length;
int width;
}res[100];
//存储最小面积包含的所有方案。
int max(int a,int b)
{
return a>b?a:b;
}
int max(int a,int b,int c)
{
return max(max(a,b),c);
}
int max(int a,int b,int c,int d)
{
return max(max(a,b,c),d);
}
int cmp(const void* m,const void* n)
{
return (*(result*)m).width-(*(result*)n).width;
}
void change()
//根据order[]和t[]来生成tmp[]。
{
for(int i=0;i<4;i++)
for(int j=0;j<=1;j++)
tmp[i][j]=rect[order[i]][j];
//顺序处理
for(int i=0;i<4;i++)
if(t[i])
swap(tmp[i][0],tmp[i][1]);
//翻转处理
}
void updata(int length,int width)
//根据当前大矩形长宽来更新res[]。
{
if(length<width)
//应题目的格式要求
swap(length,width);
if(length*width<min_size)
//当前大矩形的面积比min_size小时，更新minsize和res[]还有total以及mark[]。
{
total=1;
res[0].length=length;
res[0].width=width;
min_size=length*width;
mark.clear();
mark[width]=true;
}
else if(length*width==min_size&&!mark[width])
//当前大矩形的面积与min_size相等且有新方案时，更新res[]和total。
{
res[total].length=length;
res[total++].width=width;
mark[width]=true;
}
}
void plan_1()
//根据题目所给的图，考虑5种情况（第4、第5个图为同一种情况）。根据每种情况求出大矩形的长宽。
{
int width=tmp[0][1]+tmp[1][1]+tmp[2][1]+tmp[3][1];
int length=max(tmp[0][0],tmp[1][0],tmp[2][0],tmp[3][0]);
updata(length,width);
}
void plan_2()
{
int width=max(tmp[0][1]+tmp[1][1]+tmp[2][1],tmp[3][1]);
int length=max(tmp[0][0],tmp[1][0],tmp[2][0])+tmp[3][0];
updata(length,width);
}
void plan_3()
{
int width=max(tmp[0][1]+tmp[1][1],tmp[2][1])+tmp[3][1];
int length=max(max(tmp[0][0],tmp[1][0])+tmp[2][0],tmp[3][0]);
updata(length,width);
}
void plan_4()
{
if(tmp[0][1]<=tmp[1][1])
{
int width=tmp[1][1]+tmp[2][1]+tmp[3][1];
int length=max(tmp[0][0]+tmp[1][0],tmp[2][0],tmp[3][0]);
updata(length,width);
}
}
void plan_5()
{
if(tmp[0][1]<=tmp[1][1]&&tmp[1][0]<=tmp[3][0]&&tmp[0][1]+tmp[2][1]<=tmp[1][1]+tmp[3][1])
{
int width=tmp[1][1]+tmp[3][1];
int length=max(tmp[0][0]+tmp[1][0],tmp[2][0]+tmp[3][0]);
updata(length,width);
}
}
void get_min()
//针对change()及plan_*()的调用。
{
change();
plan_1();
plan_2();
plan_3();
plan_4();
plan_5();
}
void func()
{
for(int i=0;i<24;i++)
//四个数的全排列共有4!=24种情况。
{
for(t[0]=0;t[0]<=1;t[0]++)
for(t[1]=0;t[1]<=1;t[1]++)
for(t[2]=0;t[2]<=1;t[2]++)
for(t[3]=0;t[3]<=1;t[3]++)
//4个矩形翻转共有2^4=16种情况。
get_min();
next_permutation(&order[0],&order[4]);
//调用next_permutation()寻找order[]的下一个排列。
}
}
int main()
{
freopen("packrec.in","r",stdin);
freopen("packrec.out","w",stdout);
for(int i=0;i<4;i++)
scanf("%d%d",&rect[i][0],&rect[i][1]);
func();
qsort(res,total,sizeof(res[0]),cmp);
printf("%d\n",min_size);
for(int i=0;i<total;i++)
printf("%d %d\n",res[i].width,res[i].length);
}