[USACO] 铺放矩形块 题解

题目大意：

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

思路：

　　枚举矩形的安放顺序，再按照题目所给的图判断即可，主要要想到枚举。

代码：

 #include<bits/stdc++.h>
 using namespace std;
 int i,n,sum=,p[],q[],a[],b[];
 struct data { int x,y; }ans[];
 bool used[]; bool cmp(data a,data b) { return a.x<b.x; } void pd(int l,int r)
 {
     if (l*r<sum)
     {
         sum=l*r,ans[n=].x=l,ans[].y=r;
         if (l>r) swap(ans[].x,ans[].y);
         return;
     }
     if (l*r==sum)
     {
         ans[++n].x=l,ans[n].y=r;
         if (l>r) swap(ans[n].x,ans[n].y);
     }
 } void dfs(int k)
 {
     if (k>)
     {
         int l=,r=,i;
         for (i=;i<;i++) l=max(l,p[i]),r+=q[i];
         pd(l,r);//
         for (l=r=,i=;i<;i++) l=max(l,p[i]),r+=q[i];
         pd(l+p[],max(r,q[]));//
         l=max(p[],p[])+p[],r=max(q[]+q[],q[]);
         pd(max(l,p[]),r+q[]);//
         l=max(p[],p[]),r=max(q[],q[]);
         pd(l+p[]+p[],max(r,q[]+q[]));//
         l=max(p[]+p[],p[]+p[]);
         if (q[]>=q[])
             if (q[]>q[]) pd(l,q[]+q[]);
             else
                 if (p[]+p[]<=l) pd(l,max(q[]+q[],q[]+q[]));//
         return;
     }
     for (int i=;i<;i++)
         if (!used[i])
         {
             used[i]=;
             p[k]=a[i],q[k]=b[i],dfs(k+);
             p[k]=b[i],q[k]=a[i],dfs(k+);
             used[i]=;
         }
 } int main()
 {
     for (i=;i<;i++) scanf("%d%d",&a[i],&b[i]);
     dfs(),sort(ans+,ans+n+,cmp),printf("%d\n",sum);
     printf("%d %d\n",ans[].x,ans[].y);
     for (i=;i<=n;i++)
         if (ans[i].x!=ans[i-].x) printf("%d %d\n",ans[i].x,ans[i].y);
     return ;
 }