Распределение прямоугольников в прямоугольнике Опции

[ufna]

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

Я с таким типом алгоритмов не работал, не подскажете куда копать?

[kwisp]

Задача решается полным перебором,

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

задачка я вам скажу не тривиальная.
если не ошибаюсь на этом построен один из методов шифрования. нам препод, показывал как легко разрезать открытку на n фигур и как становится тяжело собрать при увеличении числа n. функции подобного рода имеют даже свое название в математике.

я думаю тут надо рыть в геометрию, комбинаторику,
может быть в LaTeX -- он вроде занимается размещением прямоугольников.

Сообщение отредактировал kwisp - 21.7.2009, 14:34