Подходящие прямоугольники в наименьшей возможной области

IOI 95

Шесть основных макетов четырех прямоугольников

Даны четыре прямоугольника. Найдите самый маленький прямоугольник (новый), в который эти четыре могут быть установлены без перекрытия. Наименьшим прямоугольником мы называем ту, которая имеет наименьшую площадь.

Все четыре прямоугольника должны иметь свои стороны параллельно соответствующим сторонам охватывающего прямоугольника. На рисунке 1 показаны шесть способов совмещения четырех прямоугольников. Эти шесть являются единственными возможными базовыми макетами, так как любой другой макет может быть получен из основного макета путем вращения или отражения. Прямоугольники могут поворачиваться на 90 градусов во время упаковки.

Может существовать несколько различных прямоугольников, удовлетворяющих требованиям, все с той же областью. Вы должны создать все такие прямоугольники.

ФОРМАТ INPUT
Четыре строки, каждая из которых содержит два положительных целых числа, разделенных пробелами, которые представляют длины прямоугольника с двух сторон. Каждая сторона прямоугольника имеет не менее 1 и не более 50.

ФОРМАТ ВЫХОДА
Выходной файл содержит одну строку больше, чем количество решений. Первая строка содержит одно целое число: минимальная площадь прямоугольников. Каждая из следующих строк содержит одно решение, описываемое двумя числами p и q с p <= q. Эти строки должны быть отсортированы в порядке возрастания p и должны быть разными.

Итак, это выражение о проблеме. Я понял, что хочу попробовать все 24 * 16 позиций (вы можете поворачивать прямоугольник на 90 градусов) против всех этих основных макетов и проверять новую область, однако я не знаю, как это реализовать. Все, что угодно от какого-либо псевдокода, до ссылок на статьи, поможет многим. Спасибо заранее.

Ответ 1

В то время как в Google появляются некоторые решения, я думаю, что некоторые описания высокого уровня позволят вам решить это самостоятельно.

Вы можете начать с наименования прямоугольников в каждом из 6 макетов 1,2,3,4. Затем вы должны иметь возможность вычислить ограничительную рамку для каждого из макетов для заданных экземпляров прямоугольников 1... 4 (подсказка для первого случая: width = сумма ширины 1... 4, height = max отвесов 1... 4)

Затем, как вы сказали, вы можете попробовать все возможные комбинации именования четырех заданных прямоугольников с индексами 1... 4 плюс для каждой такой возможности попробовать все возможные вращения и определить минимум по всем таким возможностям во всех макетах случаев.

Ответ 2

Поскольку существует только четыре прямоугольника, необходимо перечислить все возможные макеты. Конечно, действительно все возможные макеты слишком велики, но мы можем объединить эквивалентные макеты.

Рассмотрим только макеты, в которых каждый прямоугольник нельзя перемещать влево и вверх. Это означает, что его верхняя граница касается чего-то, а ее левая граница что-то касается. Все другие макеты могут быть преобразованы в такое подмножество, не увеличивая размер рамки.

Когда мы выбираем первый прямоугольник (один из четырех), он может касаться только левой и верхней границ ограничивающей рамки, поэтому у нас есть только одно возможное положение для его левой вершины.

Когда мы выбираем второй прямоугольник (один из трех), его верхняя граница может касаться либо верхней границы ограничивающего прямоугольника, либо нижней границы первого прямоугольника - 2 варианта. Аналогично, его левая граница может касаться либо левой границы ограничивающего прямоугольника, либо правой границы первого прямоугольника - еще двух параметров. Таким образом, мы получаем 2x2 = 4 опции для координаты его левой вершины.

И так далее для третьего и четвертого прямоугольников.

Конечно, мы должны проверить на каждом шаге, что между прямоугольниками нет пересечения (например, если оба они будут начинаться с левого верхнего угла ограничивающей рамки). Также мы иногда получаем явно неоптимальные макеты (например, когда левая вершина второго прямоугольника совпадает с правой нижней вершиной первого), но это не повредит результат и может быть удалено, если решение не достаточно быстро.

Ответ 3

в принципе, вся комбинация 24 * 16 данного прямоугольника может быть получена из приведенных выше 6 диаграмм, показанных с учетом отражения и вращения, и даже перестановки прямоугольников