USACO Packing Rectangles

March 27, 2010
这题真BT……. 题解：http://starforever.blog.hexun.com/2097115_d.html 自己最开始毫无头绪，上网搜了题解。。最后一种情况要仔细考虑，每个矩形还要翻转。。还要注意输出。
/*
ID: djgreen1
LANG: C
PROB: packrec
*/
#include <stdio.h>
#include <stdbool.h>
struct box
{
    int h,w;
};
struct box rectangle[6],rect[6],ans[6];
bool used[6],ro[6];
int p,s=10000,w,h;

int max(int a,int b)
{
    if (a>b) return a;
    else return b;
}
void judge()
{
    int i,j,temp;
    if (w>h)
    {
        temp=w;
        w=h;
        h=temp;
    }    
    if (w*h<=s)
    {
        if (w*h==s) 
        {
            for (i=1;i<=p;i++) 
            if (w==ans[i].w) return;
            for (i=1;i<=p;i++)
            if (w<ans[i].w)
            {
                for (j=p+1;j>i;j--)ans[j]=ans[j-1];
                ans[i].w=w;
                ans[i].h=h;
                p++;
                return;
            }
            p++;
            ans[p].h=h;
            ans[p].w=w;
        }    
        else
        {
            s=w*h;
            p=1;
            ans[p].h=h;
            ans[p].w=w;
        }
    }
}
void work()
{    
    //Case 1
    w=rect[1].w+rect[2].w+rect[3].w+rect[4].w;
    h=max(rect[1].h,rect[2].h);
    h=max(h,rect[3].h);
    h=max(h,rect[4].h);
    judge();
             
    //Case 2
    w=max(rect[1].w+rect[2].w+rect[3].w,rect[4].w);
    h=max(rect[1].h,rect[2].h);
    h=max(h,rect[3].h);
    h+=rect[4].h;
    judge();
    
    //Case 3
    w=max(rect[1].w+rect[2].w,rect[3].w)+rect[4].w;
    h=max(max(rect[1].h,rect[2].h)+rect[3].h,rect[4].h);
    judge();
    
    //Case 4
    w=rect[1].w+max(rect[2].w,rect[3].w)+rect[4].w;
    h=max(rect[1].h,rect[4].h);
    h=max(h,rect[2].h+rect[3].h);
    judge();
    
    //Case 6
    if (rect[3].h>=rect[2].h+rect[4].h)
    {
        w=max(rect[3].w+rect[2].w,rect[3].w+rect[4].w);
        w=max(w,rect[1].w);
        h=rect[1].h+rect[3].h;
        judge();
        return;
    }
    if (rect[3].h>rect[4].h)
    {
        w=max(rect[1].w+rect[2].w,rect[2].w+rect[3].w);
        w=max(w,rect[4].w+rect[3].w); 
        h=max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
        judge();
        return;
    }
    if (rect[3].h==rect[4].h)
    {
        w=max(rect[1].w+rect[2].w,rect[3].w+rect[4].w);
        h=max(rect[1].h,rect[2].h)+rect[3].h;
        judge();
        return;
    }
    if (rect[3].h<rect[4].h && rect[4].h<rect[3].h+rect[1].h)
    {
        w=max(rect[1].w+rect[2].w,rect[1].w+rect[4].w);
        w=max(w,rect[3].w+rect[4].w);
        h=max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
        judge();
        return;
    }
    w=max(rect[2].w,rect[1].w+rect[4].w);
    w=max(w,rect[3].w+rect[4].w);
    h=rect[4].h+rect[2].h;
    judge();    
}
void exchange(int i)
{
    int temp;
    temp=rect[i].h;
    rect[i].h=rect[i].w;
    rect[i].w=temp;
}    
void rotate(int depth)
{
    if (depth==5)
    {
        work();
        return;
    }
    if (!ro[depth])
    {
        ro[depth]=true;
        exchange(depth);
        rotate(depth+1);
        ro[depth]=false;
        exchange(depth);
        rotate(depth+1);
    }    
}        
void search(int depth)
{
    int i;
    if (depth==5)
    {
        rotate(1);
        return;
    }
    for (i=1;i<5;i++)
    {
        if (!used[i])
        {
            rect[depth]=rectangle[i];
            used[i]=true;
            search(depth+1);
            used[i]=false;
        }
    }
}                
    
int main()
{
    int i;
    FILE *in=fopen("packrec.in","r"),*out=fopen("packrec.out","w");
    
    memset(ans,0,sizeof(ans));
    for (i=1;i<5;i++) fscanf(in,"%d%d",&rectangle;[i].h,&rectangle;[i].w);
    fclose(in);
    search(1);
    fprintf(out,"%d\n",s);
    for (i=1;i<=p;i++)
    {
        fprintf(out,"%d %d\n",ans[i].w,ans[i].h);
    }
    fclose(out);
}    

```