[USACO1.4] Packing Rectangles – 分类讨论

给定 (4) 个矩形块，找一个面积最小的大矩形，使得四个小矩形可以平行地被放入其中。求所有解的长宽。

Solution

题目很良心，帮我画好了图

1. 四个矩形沿宽方向直接排布，那么总宽就是宽和，总长就是最大长
2. 一个矩形铺下面，剩下三个矩形沿宽方向排布
3. 有两个矩形铺成一个 L 形，其它两个矩形依次排布
4. 有两个矩形合成一个矩形，这样得到的三个矩形沿宽方向排布
5. 最后一种情况我觉得可以等效为四个矩形分别铺在四个角，但是要讨论一下合法性

#include <bits/stdc++.h>
using namespace std;
#define make push_back
int ans=1e9;

struct pii {
    int x,y;
    void calc() {
        if(x>y) swap(x,y);
    }
    bool operator < (const pii &b) {
        if(x!=b.x) return x < b.x;
        return y < b.y;
    }
    bool operator == (const pii &b) const {
        return x==b.x && y==b.y;
    }
};

vector <pii> v,vv;

namespace solver {
    int x[5],y[5];
    void solve1() {
        int w=0,h=0;
        w=x[1]+x[2]+x[3]+x[4];
        h=max(max(y[1],y[2]),max(y[3],y[4]));
        ans=min(ans,w*h);
        if(w*h==ans) {
            v.make({w,h});
        }
    }
    void solve2() {
        int w=0,h=0;
        w=max(x[1],x[2]+x[3]+x[4]);
        h=y[1]+max(max(y[2],y[3]),y[4]);
        ans=min(ans,w*h);
        if(w*h==ans) {
            v.make({w,h});
        }
    }
    void solve3() {
        int w=0,h=0;
        w=x[1]+max(x[2],x[3]+x[4]);
        h=max(y[1],y[2]+max(y[3],y[4]));
        ans=min(ans,w*h);
        if(w*h==ans) {
            v.make({w,h});
        }
    }
    void solve4() {
        int w=0,h=0;
        w=max(x[1],x[2])+x[3]+x[4];
        h=max(y[1]+y[2],max(y[3],y[4]));
        ans=min(ans,w*h);
        if(w*h==ans) {
            v.make({w,h});
        }
    }
    void solve5() {
        int w=0,h=0;
        w=max(x[1]+x[2],x[3]+x[4]);
        h=max(y[1]+y[3],y[2]+y[4]);
        if(x[1]+x[4]>w&&y[1]+y[4]>h) {
            if((x[1]+x[4])*h<(y[1]+y[4])*w) w=x[1]+x[4];
            else h=y[1]+y[4];
        }
        if(x[2]+x[3]>w&&y[2]+y[3]>h) {
            if((x[2]+x[3])*h<(y[2]+y[3])*w) w=x[2]+x[3];
            else h=y[2]+y[3];
        }
        ans=min(ans,w*h);
        if(w*h==ans) {
            v.make({w,h});
        }
    }
}

int w[5],h[5],p[5];

signed main() {
    for(int i=1;i<=4;i++) cin>>w[i]>>h[i];
    for(int i=0;i<1<<4;i++) {
        for(int j=1;j<=4;j++) p[j]=j;
        do {
            for(int j=1;j<=4;j++) {
                if(i&(1<<(j-1))) {
                    solver::x[j]=w[p[j]];
                    solver::y[j]=h[p[j]];
                }
                else {
                    solver::x[j]=h[p[j]];
                    solver::y[j]=w[p[j]];
                }
            }
            solver::solve1();
            solver::solve2();
            solver::solve3();
            solver::solve4();
            solver::solve5();
        } while(next_permutation(p+1,p+5));
    }
    cout<<ans<<endl;
    for(int i=0;i<v.size();i++) v[i].calc();
    sort(v.begin(),v.end());
    vv.push_back({0,0});
    for(int i=0;i<v.size();i++) {
        if(!(vv.back()==v[i]) && v[i].x*v[i].y==ans) vv.push_back(v[i]);
    }
    for(int i=1;i<vv.size();i++) cout<<vv[i].x<<" "<<vv[i].y<<endl;
}