подгонка прямоугольников на минимально возможной площади

Question

IOI 95

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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