1.4.1 Packing Rectangles 铺放矩形块 (IOI 95)

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;
}
              

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注