首页 > 代码库 > 【USACO 1.4.1】铺放矩形块

【USACO 1.4.1】铺放矩形块

2024-07-08 00:13:07   222人阅读

【描述】

给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。
 
 
 
 
 
 
 

所有4个矩形块的边都与封闭矩形的边相平行，图1示出了铺放4个矩形块的6种方案。这6种方案是仅可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。

可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。

（分类注解：这里的分类依据可以视为是不同的面积计算公式。）

【格式】

INPUT FORMAT:
(file packrec.in)
共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。
OUTPUT FORMAT:
(file packrec.out)
总行数为解的总数加1。第一行是一个整数，代表封闭矩形的最小面积（子任务A）。接下来的每一行都表示一个解，由数P和数Q来表示，并且P≤Q（子任务B）。这些行必须根据P的大小按升序排列，P小的行在前，大的在后。且所有行都应是不同的。

【分析】

对于这道题，我只能说诡异......

实际上，如果把题目中的4个矩形变成n个矩形，这会是一道相当难的题目，但是在题目中给定了限制条件之后，求解变得可能了。

怎么说呢？情况数很多，但是仔细思考后并不是特别难，只是要注意特殊情况。

附参考：http://hi.baidu.com/nash635/item/6619502e7b9020f851fd8701

代码有点丑了......

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <algorithm>
  6 const int maxn=15;
  7 using namespace std;
  8 struct matrix
  9 {
 10        int w;
 11        int h;
 12 }data[maxn];
 13 struct Ans
 14 {
 15        int w;
 16        int h;
 17        int s;
 18        bool operator <(const Ans&b) const
 19        {
 20             if (s==b.s) return w<b.w;
 21             return s<b.s;
 22        }
 23 }ans[60000];
 24 int point=0;
 25 void check(matrix a,matrix b,matrix c,matrix d);
 26 int main()
 27 {
 28     int i,a,b,c,d;
 29     int vis[15];
 30     //文件操作 
 31     freopen("packrec.in","r",stdin);
 32     freopen("packrec.out","w",stdout);
 33     for (i=1;i<=4;i++)
 34     {
 35         scanf("%d%d",&data[i].w,&data[i].h);
 36         data[i+4].w=data[i].h;
 37         data[i+4].h=data[i].w;//不同的擺放狀態也應該記作不同的矩形 
 38     }
 39     
 40     for (a=1;a<=8;a++)
 41     for (b=1;b<=8;b++)
 42     {
 43         if (a==b) continue;
 44         for (c=1;c<=8;c++)
 45         {
 46             if (a==c || b==c) continue;
 47             for (d=1;d<=8;d++)
 48             {
 49                 if (a==d || b==d || c==d) continue;
 50                 memset(vis,0,sizeof(vis));
 51                 vis[a]++;vis[b]++;vis[c]++;vis[d]++;
 52                 if (vis[1]+vis[5]>1) continue;
 53                 if (vis[2]+vis[6]>1) continue;
 54                 if (vis[3]+vis[7]>1) continue;
 55                 if (vis[4]+vis[8]>1) continue;
 56                 check(data[a],data[b],data[c],data[d]);
 57             }
 58         }
 59     }
 60 
 61     sort(ans,ans+point);
 62     printf("%d\n",ans[0].s);
 63     for (i=0;i<point;i++)
 64     {
 65         if (i!=0 && ans[i].s!=ans[i-1].s) break;
 66         if (i!=0 && ans[i].w==ans[i-1].w) continue;
 67         printf("%d %d\n",ans[i].w,ans[i].h);
 68     }
 69     return 0;
 70 }
 71 void check(matrix a,matrix b,matrix c,matrix d)
 72 {
 73      //枚舉
 74      ans[point].w=a.w+b.w+c.w+d.w;ans[point].h=max(a.h,max(b.h,max(c.h,d.h))); 
 75      ans[point].s=ans[point].w*ans[point].h;
 76      if (ans[point].w>ans[point].h) swap(ans[point].w,ans[point].h);
 77      point++;
 78      ans[point].w=max(a.w+b.w+c.w,d.w);ans[point].h=max(a.h,max(b.h,c.h))+d.h;
 79      ans[point].s=ans[point].w*ans[point].h;
 80      if (ans[point].w>ans[point].h) swap(ans[point].w,ans[point].h);
 81      point++;
 82      ans[point].w=max(a.w+b.w,c.w)+d.w;
 83      ans[point].h=max(a.h+c.h,max(b.h+c.h,d.h));
 84      ans[point].s=ans[point].w*ans[point].h;
 85      if (ans[point].w>ans[point].h) swap(ans[point].w,ans[point].h);
 86      point++;
 87      ans[point].w=a.w+b.w+max(c.w,d.w);
 88      ans[point].h=max(a.h,max(c.h+d.h,b.h));
 89      ans[point].s=ans[point].w*ans[point].h;
 90      if (ans[point].w>ans[point].h) swap(ans[point].w,ans[point].h);
 91      point++;
 92      ans[point].h=max(a.h+c.h,b.h+d.h);
 93      if (c.h==d.h) ans[point].w=max(a.w+b.w,c.w+d.w);
 94      if (c.h>=b.h+d.h) ans[point].w=max(a.w,max(c.w+b.w,c.w+d.w));
 95      if (c.h>d.h && c.h<b.h+d.h) ans[point].w=max(a.w+b.w,max(b.w+c.w,c.w+d.w));
 96      if (d.h>c.h && d.h<a.h+c.h) ans[point].w=max(a.w+b.w,max(a.w+d.w,c.w+d.w));
 97      if (d.h>=a.h+c.h) ans[point].w=max(b.w,max(a.w+d.w,c.w+d.w));
 98      ans[point].s=ans[point].w*ans[point].h;
 99      if (ans[point].w>ans[point].h) swap(ans[point].w,ans[point].h);
100      point++;
101 }

 


联系
我们