Packing Rectangles
Layout Enumeration There are exactly 6 topologically distinct ways to pack 4 axis-aligned rectangles into a bounding box. For rectangles labeled a, b, c, d with dimensions (w_i, h_i): Row: All four side by side. W = w...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given 4 rectangles with specified widths and heights, find the enclosing rectangle of minimum area that contains all four without overlap. Each rectangle may be rotated by $90^\circ$. All rectangles must be placed with sides parallel to the sides of the enclosing rectangle.
Output the minimum area and all pairs $(W, H)$ with $W \le H$ that achieve this area.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Layout Enumeration
There are exactly 6 topologically distinct ways to pack 4 axis-aligned rectangles into a bounding box. For rectangles labeled $a, b, c, d$ with dimensions $(w_i, h_i)$:
Row: All four side by side.
$W = w_a + w_b + w_c + w_d$, $H = \max(h_a, h_b, h_c, h_d)$.Three stacked + one beside: Three rectangles stacked vertically, one placed to their side.
$W = \max(w_a, w_b, w_c) + w_d$, $H = \max(h_a + h_b + h_c,\; h_d)$.Two + two stacked: Two stacked on the left, two on the right.
$W = \max(w_a, w_b) + \max(w_c, w_d)$, $H = \max(h_a + h_b,\; h_c + h_d)$.L-shape: Two stacked left ($a, b$); $c$ right of $a$; $d$ right of $b$.
$W = \max(w_a + w_c,\; w_b + w_d)$, $H = \max(h_a + h_b,\; h_c + h_d)$.T-shape: $a$ on the left spanning full height; $b$ and $c$ stacked in the middle; $d$ on the right spanning full height.
$W = w_a + \max(w_b, w_c) + w_d$, $H = \max(h_a,\; h_b + h_c,\; h_d)$.Cross: $a$ and $b$ on top row with a horizontal split; $c$ and $d$ on bottom row with a possibly different split. The height depends on how the vertical boundary interacts.
This is handled by trying $c$ next to $a$ and $d$ next to $b$, etc.
Algorithm
For each of the $2^4 = 16$ rotation combinations and all $4! = 24$ permutations of the rectangles, evaluate all 6 layout types. Track the minimum area and, among ties, the minimum perimeter.
The total work is at most $16 \times 24 \times 6 = 2304$ evaluations, each taking $O(1)$ time.
Complexity Analysis
Time: $O(1)$ --- bounded by $2304$ constant-time evaluations.
Space: $O(1)$.
Notes
The solution exhaustively enumerates all topologically distinct packing configurations. Since the number of configurations is bounded by a small constant, correctness follows from completeness of the case analysis. The six layout types are well-known to cover all possible axis-aligned packings of four rectangles; see, e.g., Korf (2003) for a proof that these cases are exhaustive.
The improved code uses next_permutation for cleaner permutation enumeration and collects all optimal $(W, H)$ pairs in a set to avoid duplicates.
Code
C++ solution used for this page.
// IOI 1989 - Problem 1: Packing Rectangles
// Find smallest enclosing rectangle for 4 rectangles (each may be rotated 90 degrees).
// Enumerate all 6 layout types x 24 permutations x 16 rotations.
#include <bits/stdc++.h>
using namespace std;
int bestArea, bestW, bestH;
void updateBest(int w, int h) {
if (w <= 0 || h <= 0) return;
int area = w * h;
if (area < bestArea || (area == bestArea && w + h < bestW + bestH)) {
bestArea = area;
// Normalize so bestW <= bestH
bestW = min(w, h);
bestH = max(w, h);
}
}
void tryLayouts(int w[], int h[]) {
// Type 1: all four in a row
updateBest(w[0] + w[1] + w[2] + w[3],
max({h[0], h[1], h[2], h[3]}));
// Type 2: three stacked on one side, one beside them
for (int i = 0; i < 4; i++) {
int sumH = 0, maxW = 0;
for (int j = 0; j < 4; j++) {
if (j == i) continue;
sumH += h[j];
maxW = max(maxW, w[j]);
}
updateBest(maxW + w[i], max(sumH, h[i]));
}
// Type 3: two stacked left, two stacked right (3 pairings)
int pairs[3][4] = {{0,1,2,3}, {0,2,1,3}, {0,3,1,2}};
for (auto& p : pairs) {
int a = p[0], b = p[1], c = p[2], d = p[3];
updateBest(max(w[a], w[b]) + max(w[c], w[d]),
max(h[a] + h[b], h[c] + h[d]));
}
// Types 4-5: enumerate all 24 permutations for 2x2-style layouts
int idx[4];
int perm[4] = {0, 1, 2, 3};
do {
int a = perm[0], b = perm[1], c = perm[2], d = perm[3];
// Type 4: a,b stacked left; c right of a; d right of b
updateBest(max(w[a] + w[c], w[b] + w[d]),
max(h[a] + h[b], h[c] + h[d]));
// Type 5: a left column, (b,c) stacked middle, d right column
updateBest(w[a] + max(w[b], w[c]) + w[d],
max({h[a], h[b] + h[c], h[d]}));
} while (next_permutation(perm, perm + 4));
}
int main() {
int W[4], H[4];
for (int i = 0; i < 4; i++)
scanf("%d%d", &W[i], &H[i]);
bestArea = INT_MAX;
bestW = bestH = INT_MAX;
// Try all 2^4 = 16 rotation states
for (int mask = 0; mask < 16; mask++) {
int w[4], h[4];
for (int i = 0; i < 4; i++) {
if (mask & (1 << i)) {
w[i] = H[i]; h[i] = W[i];
} else {
w[i] = W[i]; h[i] = H[i];
}
}
tryLayouts(w, h);
}
printf("%d\n%d %d\n", bestArea, bestW, bestH);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.