USACO Training>My Training>Section 1.4>Packing Rectangles

Packing Rectangles

The six basic layouts of four rectangles:

Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.

All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.

There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.

PROGRAM NAME: packrec

INPUT FORMAT
Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle's two sides. Each side of a rectangle is at least 1 and at most 50.

SAMPLE INPUT (file packrec.in) 

1 2
2 3
3 4
4 5

OUTPUT FORMAT
The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.

SAMPLE OUTPUT (file packrec.out)

40
4 10
5 8

Solution (Me)


/*
ID: sgospod1
PROG: packrec
LANG: C++
*/
#include <stdio.h>
#include <string.h> 
#include <time.h> 
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <fstream>

#define STANDARD_INPUT
/*#define PRINT_DEBUG*/

#define RECT_COUNT 4
#define LAYOUTS_COUNT 6

using namespace std;

typedef struct 
{
    int Width;
    int Height;
} Rectangle;

Rectangle rect[RECT_COUNT];

int S=100000; /*  */
int Sm = 0;
int SolutionCount = 0;
Rectangle Solutions[100];
int mask[4] = {0,0,0,0};
int layout = 0;
int r = 0; /* rotation */

#ifdef PRINT_DEBUG
ofstream log ("log.out");
#endif    

void CheckSolution(int w, int h)
{
#ifdef PRINT_DEBUG
    log << w*h << "=" << w << '*' << h << " (" << layout << ", " << r << "/" << mask[3] << mask[2] << mask[1] << mask[0] << endl;
#endif    
    
    int S1 = w*h;
    if(S1<Sm) return;
    if(S1>S) return;
    
    if(S1<S) /* smaller area has been found */
    {
        SolutionCount = 0;
        S = S1;
    }
    if(w>h)
    {
        int x = w;
        w = h;
        h = x;
    }
    bool found = false;
    for(int i=0; i<SolutionCount; i++)
        if(Solutions[i].Width==w) { found=true; break;}

    if(found) return;

    Solutions[SolutionCount].Width = w;
    Solutions[SolutionCount].Height = h;

    SolutionCount++;
}

int CompareRect(const void * a, const void * b)
{
    return ((Rectangle *)a)->Width - ((Rectangle *)b)->Width;
}

void Swap()
{
    for(int i=0; i<RECT_COUNT; i++)
    {
        if(mask[i])
        {
            int x = rect[i].Width;
            rect[i].Width = rect[i].Height;
            rect[i].Height = x;
        }
    }
}

void SetMask(int set)
{
    mask[0] = set & 1;
    mask[1] = set & 2;
    mask[2] = set & 4;
    mask[3] = set & 8;

}

void Layout0()
{
    int w = 0;
    int h = 0;
    for(int k=0; k<RECT_COUNT; k++)
    {
        w+=rect[k].Width;
        if(h<rect[k].Height) h=rect[k].Height;
    }
    CheckSolution(w, h);
}

void Layout1() /* i-horisontal rect */
{
    for(int i=0; i<RECT_COUNT; i++)
    {
        int w = 0, h = 0;
        for(int k=0; k<RECT_COUNT; k++)
        {
            if(k==i) continue;
            w+=rect[k].Width;
            if(h<rect[k].Height) h=rect[k].Height;
        }
        w = (w >= rect[i].Height) ? w : rect[i].Height;
        h += rect[i].Width;
        CheckSolution(w, h);
    }
}

void Layout2() /* i1 - hor, i2 - vert */
{
    for(int i=0; i<16; i++)
    {
        int w = 0, h = 0;
        int i1 = i/4;
        int i2 = i%4;
        if(i1==i2) continue;
        for(int k=0; k<RECT_COUNT; k++)
        {
            if(k==i1 || k==i2) continue;
            w+=rect[k].Width;
            if(h<rect[k].Height) h=rect[k].Height;
        }
        w = (w >= rect[i1].Height) ? w : rect[i1].Height;
        w += rect[i2].Width;
        h += rect[i1].Width;
        h = (h>= rect[i2].Height) ? h : rect[i2].Height;
        CheckSolution(w, h);
    }
}

void Layout3() /* i1-vertical rect up, i2 - vertical rect down */
{
    for(int i=0; i<16; i++)
    {                
        int w = 0, h = 0;
        int i1 = i/4;
        int i2 = i%4;
        if(i1==i2) continue;
        for(int k=0; k<RECT_COUNT; k++)
        {
            if(k==i2 || k==i1) continue;
            w+=rect[k].Width;
            if(h<rect[k].Height) h=rect[k].Height;
        }
        w += (rect[i2].Width>=rect[i1].Width) ? rect[i2].Width : rect[i1].Width;
        int h1 = rect[i2].Height + rect[i1].Height;
        h = (h>=h1) ? h : h1;
        CheckSolution(w, h);
    }
}

void CombineRect(int *v, const int start, const int n)
{  
  if (start == n-1) 
  {
    int w = 0, h = 0;
    h = rect[v[0]].Height + rect[v[1]].Height;
    h = (rect[v[2]].Height + rect[v[3]].Height) > h ? (rect[v[2]].Height + rect[v[3]].Height) : h;
    int hdif = rect[v[1]].Height - rect[v[2]].Height;

    w += rect[v[1]].Width + rect[v[2]].Width;
    int wdif1 = rect[v[0]].Width - rect[v[1]].Width;
    int wdif2 = rect[v[3]].Width - rect[v[2]].Width;
    if(wdif1>0 && wdif2>0) w += wdif1 + wdif2;
    else if(wdif1>0)
    {
        if(hdif>=0 && abs(hdif)<rect[v[3]].Height && (wdif1+rect[v[3]].Width > rect[v[2]].Width)) w+= (wdif1+rect[v[3]].Width - rect[v[2]].Width);
        else if(hdif>=0 && abs(hdif)>=rect[v[3]].Height && (wdif1 > rect[v[2]].Width)) w+= wdif1 - rect[v[2]].Width;
        else if(hdif<0) w+=wdif1;
    }
    else if(wdif2>0)
    {
        if(hdif<0 && abs(hdif)<rect[v[0]].Height && (wdif2+rect[v[0]].Width > rect[v[1]].Width)) w+= (wdif2+rect[v[0]].Width - rect[v[1]].Width);
        else if(hdif<0 && abs(hdif)>=rect[v[0]].Height && (wdif2 > rect[v[1]].Width)) w+= wdif2 - rect[v[1]].Width;
        else if(hdif>=0) w+=wdif2;
    }


#ifdef PRINT_DEBUG
    log << w*h << "=" << w << '*' << h << " (" << layout << ", " << r << "/" << mask[3] << mask[2] << mask[1] << mask[0] << ", " << v[0] << v[1] << v[2] << v[3] << ")" << endl;
#endif

    CheckSolution(w, h);  
  }
  else 
  {
    for (int i = start; i < n; i++) 
    {
      int tmp = v[i];     
      v[i] = v[start];
      v[start] = tmp;
      CombineRect(v, start+1, n);
      v[start] = v[i];
      v[i] = tmp;
    }
  }
}

void Layout5() 
{
    int v[] = {0, 1, 2, 3};
    CombineRect(v, 0, sizeof(v)/sizeof(int));
}

int main()
{
#ifdef PRINT_DEBUG
    time_t currtime;
    currtime = time(NULL);
    cerr << "Start time: " << ctime(&currtime) << endl;
#endif
#ifdef STANDARD_INPUT
    istream &fin = cin;
    ostream &fout = cout;
#else
    ofstream fout ("packrec.out");
    ifstream fin ("packrec.in");
#endif
    assert(fin != NULL && fout != NULL);

    for(int i=0; i<RECT_COUNT; i++)
    {
        fin >> rect[i].Width >> rect[i].Height;
        Sm += rect[i].Width * rect[i].Height;
    }

    for(r=0; r<16; r++)
    {
        SetMask(r);
        Swap();
        for(layout=0; layout<LAYOUTS_COUNT; layout++)
        {
            if(layout==4) continue;
            int w =0;
            int h =0;
            if(layout==0) Layout0();
            else if(layout==1) Layout1();
            else if(layout==2) Layout2();
            else if(layout==3 || layout==4) Layout3();
            else if(layout==5) Layout5();
        }
        Swap(); //swap back
    }

    fout << S << endl;
    qsort(Solutions, SolutionCount,sizeof(Rectangle),CompareRect);
    for(int i=0; i<SolutionCount; i++) 
        fout << Solutions[i].Width << " " << Solutions[i].Height << endl;
#ifdef PRINT_DEBUG
    currtime = time(NULL);
    cerr << "End time: " << ctime(&currtime) << endl;
#endif
    return 0;
}

All solutions

Tests
Input Output