Упаковка прямоугольников
http://acm.pku.edu.cn/JudgeOnline/problem?id=1169
Даны четыре прямоугольника. Найдите наименьший покрывающий их (новый) прямоугольник, в который могут поместиться без перекрытий заданные 4 прямоугольника. Под наименьшим мы понимаем прямоугольник наименьшей площади.
Стороны всех четырех прямоугольников должны быть параллельны соответствующим сторонам сторонам покрывающего прямоугольника. На рисунке выше показано шесть совместного размещения четырех прямоугольников. Эти шесть примеров исчерпывают все структуры, так как любая другая структура может быть получена из некоторой приведенной поворотами и (или) отражениями. Могут существовать покрывающие прямоугольники с различными длинами сторон, удовлетворяющие условиям и имеющим минимальную площадь. Вы должны получить все такие покрывающие прямоугольники.
Входные данные
Входные данные состоят из четырех строк. Каждая строка описывает один исходный прямоугольник двумя положительными целыми числами - длинами сторон прямоугольника. Каждая сторона прямоугольника имеет длину не менее 1 м и не более 50.
Выходные данные
Вывести на одну строку больше, чем существует решений. Первая строка должна содержать одно целое число: минимальную площадь покрывающего прямоугольника. Каждая из следующих строк должна содержать одно решение, описанное числами p и q - длинами сторон покрывающего прямоугольника; при этом должно выполняться условие p <= q. Эти строки должны быть упорядочены по возрастанию p; все они должны быть различными.
Пример входных данных
1 2
2 3
3 4
4 5
Пример выходных данных
40
4 10
5 8
Анализ условия и обсуждение идеи решения
Пример решения на С++:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef struct Rect Rect; struct Rect { int wid; int ht; }; Rect rotate(Rect r) { Rect nr; nr.wid = r.ht; nr.ht = r.wid; return nr; } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int tot; int bestarea; int bestht[101]; void record(Rect r) { int i; if(r.wid*r.ht < tot) *(long*)0=0; if(r.wid*r.ht < bestarea || bestarea == 0) { bestarea = r.wid*r.ht; for(i=0; i<=100; i++) bestht[i] = 0; } if(r.wid*r.ht == bestarea) bestht[min(r.wid, r.ht)] = 1; } void check(Rect *r) { Rect big; int i; /* schema 1: all lined up next to each other */ big.wid = 0; big.ht = 0; for(i=0; i<4; i++) { big.wid += r[i].wid; big.ht = max(big.ht, r[i].ht); } record(big); /* schema 2: first three lined up, fourth on bottom */ big.wid = 0; big.ht = 0; for(i=0; i<3; i++) { big.wid += r[i].wid; big.ht = max(big.ht, r[i].ht); } big.ht += r[3].ht; big.wid = max(big.wid, r[3].wid); record(big); /* schema 3: first two lined up, third under them, fourth to side */ big.wid = r[0].wid + r[1].wid; big.ht = max(r[0].ht, r[1].ht); big.ht += r[2].ht; big.wid = max(big.wid, r[2].wid); big.wid += r[3].wid; big.ht = max(big.ht, r[3].ht); record(big); /* schema 4, 5: first two rectangles lined up, next two stacked */ big.wid = r[0].wid + r[1].wid; big.ht = max(r[0].ht, r[1].ht); big.wid += max(r[2].wid, r[3].wid); big.ht = max(big.ht, r[2].ht+r[3].ht); record(big); /* * schema 6: first two pressed next to each other, next two on top, like: * 2 3 * 0 1 */ big.ht = max(r[0].ht+r[2].ht, r[1].ht+r[3].ht); big.wid = r[0].wid + r[1].wid; /* do 2 and 1 touch? */ if(r[0].ht < r[1].ht) big.wid = max(big.wid, r[2].wid+r[1].wid); /* do 2 and 3 touch? */ if(r[0].ht+r[2].ht > r[1].ht) big.wid = max(big.wid, r[2].wid+r[3].wid); /* do 0 and 3 touch? */ if(r[1].ht < r[0].ht) big.wid = max(big.wid, r[0].wid+r[3].wid); /* maybe 2 or 3 sits by itself */ big.wid = max(big.wid, r[2].wid); big.wid = max(big.wid, r[3].wid); record(big); } void checkrotate(Rect *r, int n) { if(n == 4) { check(r); return; } checkrotate(r, n+1); r[n] = rotate(r[n]); checkrotate(r, n+1); r[n] = rotate(r[n]); } void checkpermute(Rect *r, int n) { Rect t; int i; if(n == 4) checkrotate(r, 0); for(i=n; i<4; i++) { t = r[n], r[n] = r[i], r[i] = t; /* swap r[i], r[n] */ checkpermute(r, n+1); t = r[n], r[n] = r[i], r[i] = t; /* swap r[i], r[n] */ } } int main(void){ FILE *fin, *fout; Rect r[4]; int i; fin = stdin; fout = stdout; assert(fin != NULL && fout != NULL); for(i=0; i<4; i++) fscanf(fin, "%d %d", &r[i].wid, &r[i].ht); tot=(r[0].wid*r[0].ht+r[1].wid*r[1].ht+r[2].wid*r[2].ht+r[3].wid*r[3].ht); checkpermute(r, 0); fprintf(fout, "%d\n", bestarea); for(i=0; i<=100; i++) if(bestht[i]) fprintf(fout, "%d %d\n", i, bestarea/i); exit(0); }