[USACO] 1.4 Packing Rectangles

4개 사각형에서 나올 수 있는 16가지 경우에 대해 4개의 사각형의 순서 4!인 24개의 경우
즉, 16*24개의 경우에 대해 각각 6가지 유형일때 최소로 싸는 사각형을 구했다.
6번째 유형에서 겹치는 부분 처리가 안되서 몇번 틀림..

개인적으로 next_permutation 함수를 처음 써봤는데 상당히 쓸만한듯..

vector< pair<int, pair<int, int> > > ret;

bool find_cycle(int cycle[], int order)
{
    int i = 0;
    while(order > 0)
    {
        cycle[i] = order % 2;
        order /= 2;
        i++;
    }
    return true;
}

bool check_value(int a, int b, int &cur, int &x, int&y)
{
    if( cur >= a*b)
    {
        cur = a*b;
        x = min(a, b);
        y = max(a, b);
        ret.pb(make_pair(cur, make_pair(x, y)));
    }
    return true;
}

int main() {

    ofstream fout ("packrec.out");
    ifstream fin ("packrec.in");
   
    vector< vector<int> > d;
    int a, b;
    REP(i, 4)
    {
        fin >> a >> b;
        VI sub;
        sub.pb(a);
        sub.pb(b);
        d.pb(sub);
    }

    int order = 0;
    int cycle[4] = {0,0,0,0};

    int cur = INT_MAX, x = 0, y = 0;

    while(order < 16)
    {
        find_cycle(cycle, order);
        order++;

        int width[4];
        int height[4];
        REP(i, 4)
        {
            width[i] = d[i][cycle[i]];
            height[i] = d[i][1-cycle[i]];
        }

        int a = 0, b = 0;
        int step[4] = {0, 1, 2, 3};
       
        do
        {       
            //type 1
            a = width[step[0]] + width[step[1]] + width[step[2]] + width[step[3]];
            b = max( max(height[step[0]], height[step[1]]), max(height[step[2]], height[step[3]]));
            check_value(a, b, cur, x, y);

            //type 2
            a = width[step[1]] + width[step[2]] + width[step[3]];
            a = max(a, width[step[0]]);
            b = max(height[step[1]], max(height[step[2]], height[step[3]]));
            b += height[step[0]];
            check_value(a, b, cur, x, y);

            //type3
            a = max(width[step[0]], width[step[2]] + width[step[3]]);
            a += width[step[1]];
            b = max(height[step[2]], height[step[3]]) + height[step[0]];
            b = max( b, height[step[1]]);
            check_value(a, b, cur, x, y);

            //type 4 & 5
            a = width[step[0]] + width[step[3]];
            a += max( width[step[1]], width[step[2]]);           
            b = max(height[step[0]], height[step[3]]);
            b = max( b, height[step[1]] + height[step[2]]);
            check_value(a, b, cur, x, y);

            //type6
            a = max( width[step[0]] + width[step[1]], width[step[2]] + width[step[3]]);
            b = max( height[step[0]] +  height[step[3]],  height[step[1]] +  height[step[2]]);
            if( a < width[step[0]] + width[step[2]] && b < height[step[0]] +  height[step[2]])
                a = width[step[0]] + width[step[2]];
            if( a < width[step[1]] + width[step[3]] && b < height[step[1]] +  height[step[3]])
                a = width[step[1]] + width[step[3]];

            check_value(a, b, cur, x, y);
           
        }while( next_permutation(step, step+4));   
    }

    fout << cur << endl;

    sort(ALL(ret));
    ret.erase(unique(ALL(ret)), ret.end());
    for(int i=0; i < ret.size() && ret[i].first == cur ; i++)
        fout << ret[i].second.first << " " << ret[i].second.second << endl;

    return 0;
}