1.4.1 Packing Rectangles 铺放矩形块 (IOI 95)
时间： 1ms 内存：64M
描述：
给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。
图1-1
所有4个矩形块的边都与封闭矩形的边相平行，图1示出了铺放4个矩形块的6种方案。这6种方案只是可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。
输入：
共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。
输出：
总行数为解的总数加1。第一行是一个整数，代表封闭矩形的最小面积（子任务A）。接下来的每一行都表示一个解，由数P和数Q来表示，并且P≤Q（子任务B）。这些行必须根据P的大小按升序排列，P小的行在前，大的在后。且所有行都应是不同的。 //================
示例输入：
1 2
2 3
3 4
4 5
示例输出：
40
4 10
5 8
提示：
参考答案（内存最优[884]）：
/*
ID: kenneth5
PROG: packrec
LANG: C++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef struct
{
int x,y;
} node;
node ans[10000];
int p[10],CNT,MAX;
int x[10],y[10],use[10];
int cmp(node x,node y)
{
return x.x<y.x;
}
int max(int x,int y)
{
return x>y? x:y;
}
int min(int x,int y)
{
return x<y? x:y;
}
void doo(int x,int y)
{
if (MAX==-1||x*y<MAX)
{
CNT=0;
ans[CNT].x=min(x,y);
ans[CNT].y=max(x,y);
CNT++;
MAX=x*y;
}
else if (x*y==MAX)
{
ans[CNT].x=min(x,y);
ans[CNT].y=max(x,y);
CNT++;
}
}
void find(int a,int b,int c,int d)
{
int tx,ty;
tx=x[a]+x[b]+x[c]+x[d];
ty=max(y[a],max(y[b],max(y[c],y[d])));
doo(tx,ty);
tx=max(x[a],x[b]+x[c]+x[d]);
ty=y[a]+max(y[b],max(y[c],y[d]));
doo(tx,ty);
tx=x[d]+max(x[a]+x[b],x[c]);
ty=max(y[d],y[c]+max(y[a],y[b]));
doo(tx,ty);
tx=x[a]+x[d]+max(x[b],x[c]);
ty=max(y[a],max(y[b]+y[c],y[d]));
doo(tx,ty);
tx=max(x[a],x[b])+x[c]+x[d];
ty=max(y[d],max(y[c],y[a]+y[b]));
doo(tx,ty);
tx=max(x[a],x[c])+max(x[b],x[d]);
ty=max(y[a]+y[c],y[b]+y[d]);
doo(tx,ty);
if (x[c]>=x[a]&&x[b]>=x[d]&&y[d]>=y[c]&&x[a]+x[b]<=x[c]+x[d])
{
tx=x[a]+x[d]+max(x[c]-x[a],x[d]-x[b]);
ty=max(y[a]+y[c],y[b]+y[d]);
doo(tx,ty);
}
}
void change(int a)
{
int temp=x[a];
x[a]=y[a];
y[a]=temp;
}
void cal(int a,int b,int c,int d)
{
for (int i=0;i<2;i++)
{
if (i==1) change(a);
for (int j=0;j<2;j++)
{
if (j==1) change(b);
for (int k=0;k<2;k++)
{
if (k==1) change(c);
for (int l=0;l<2;l++)
{
if (l==1) change(d);
find(a,b,c,d);
if (l==1) change(d);
}
if (k==1) change(c);
}
if (j==1) change(b);
}
if (i==1) change(a);
}
}
void dfs(int layer,int num)
{
if (layer==num)
{
cal(p[0],p[1],p[2],p[3]);
return;
}
for (int i=0;i<4;i++)
{
if (!use[i])
{
use[i]=1;
p[layer]=i;
dfs(layer+1,num);
use[i]=0;
}
}
}
int main()
{
//freopen("packrec.in","r",stdin);
//freopen("packrec.out","w",stdout);
while (scanf("%d%d",&x[0],&y[0])==2)
{
for (int i=1;i<4;i++)
scanf("%d%d",&x[i],&y[i]);
memset(use,0,sizeof(use));
CNT=0;
MAX=-1;
dfs(0,4);
printf("%d\n",MAX);
sort(ans,ans+CNT,cmp);
for (int i=0;i<CNT;i++)
{
if (i!=0&&ans[i].x==ans[i-1].x) continue;
printf("%d %d\n",ans[i].x,ans[i].y);
}
}
return 0;
}
参考答案（时间最优[12]）：
/*
ID: kenneth5
PROG: packrec
LANG: C++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef struct
{
int x,y;
} node;
node ans[10000];
int p[10],CNT,MAX;
int x[10],y[10],use[10];
int cmp(node x,node y)
{
return x.x<y.x;
}
int max(int x,int y)
{
return x>y? x:y;
}
int min(int x,int y)
{
return x<y? x:y;
}
void doo(int x,int y)
{
if (MAX==-1||x*y<MAX)
{
CNT=0;
ans[CNT].x=min(x,y);
ans[CNT].y=max(x,y);
CNT++;
MAX=x*y;
}
else if (x*y==MAX)
{
ans[CNT].x=min(x,y);
ans[CNT].y=max(x,y);
CNT++;
}
}
void find(int a,int b,int c,int d)
{
int tx,ty;
tx=x[a]+x[b]+x[c]+x[d];
ty=max(y[a],max(y[b],max(y[c],y[d])));
doo(tx,ty);
tx=max(x[a],x[b]+x[c]+x[d]);
ty=y[a]+max(y[b],max(y[c],y[d]));
doo(tx,ty);
tx=x[d]+max(x[a]+x[b],x[c]);
ty=max(y[d],y[c]+max(y[a],y[b]));
doo(tx,ty);
tx=x[a]+x[d]+max(x[b],x[c]);
ty=max(y[a],max(y[b]+y[c],y[d]));
doo(tx,ty);
tx=max(x[a],x[b])+x[c]+x[d];
ty=max(y[d],max(y[c],y[a]+y[b]));
doo(tx,ty);
tx=max(x[a],x[c])+max(x[b],x[d]);
ty=max(y[a]+y[c],y[b]+y[d]);
doo(tx,ty);
if (x[c]>=x[a]&&x[b]>=x[d]&&y[d]>=y[c]&&x[a]+x[b]<=x[c]+x[d])
{
tx=x[a]+x[d]+max(x[c]-x[a],x[d]-x[b]);
ty=max(y[a]+y[c],y[b]+y[d]);
doo(tx,ty);
}
}
void change(int a)
{
int temp=x[a];
x[a]=y[a];
y[a]=temp;
}
void cal(int a,int b,int c,int d)
{
for (int i=0;i<2;i++)
{
if (i==1) change(a);
for (int j=0;j<2;j++)
{
if (j==1) change(b);
for (int k=0;k<2;k++)
{
if (k==1) change(c);
for (int l=0;l<2;l++)
{
if (l==1) change(d);
find(a,b,c,d);
if (l==1) change(d);
}
if (k==1) change(c);
}
if (j==1) change(b);
}
if (i==1) change(a);
}
}
void dfs(int layer,int num)
{
if (layer==num)
{
cal(p[0],p[1],p[2],p[3]);
return;
}
for (int i=0;i<4;i++)
{
if (!use[i])
{
use[i]=1;
p[layer]=i;
dfs(layer+1,num);
use[i]=0;
}
}
}
int main()
{
//freopen("packrec.in","r",stdin);
//freopen("packrec.out","w",stdout);
while (scanf("%d%d",&x[0],&y[0])==2)
{
for (int i=1;i<4;i++)
scanf("%d%d",&x[i],&y[i]);
memset(use,0,sizeof(use));
CNT=0;
MAX=-1;
dfs(0,4);
printf("%d\n",MAX);
sort(ans,ans+CNT,cmp);
for (int i=0;i<CNT;i++)
{
if (i!=0&&ans[i].x==ans[i-1].x) continue;
printf("%d %d\n",ans[i].x,ans[i].y);
}
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。