заполнение прямоугольника

[Ramzes]

Есть прямоугольник A? дана его площадь его площадь sA
и есть еще n прямоугольников
допустим
B площадь sB
C площадь sC
D площадь sD
E площадь sE
F площадь sF

общая площадь которых, равна площади прямоугольника A
sA = sB + sC + sD + sE + sF

Надо заполнить прямоугольник А, остальными прямоугольниками, так, что бони между собой не пересекались, и польностью заполняли прямоугольник A

[MIT]

Напоминает одно из заданий на областной олимпиаде по информатике в прошлом году... Его никто не решил.
А координаторы олимпиады потом рассказывали, что это решается как-то путем представления прямоугольника А как матрицы, состоящей из минимально допустимых частей и потом каким-то хитрым перебором его заполнения, который никто объснить не смог. Вот так вот.

[iGrok]

"Задача оптимального расположения этикеток разного размера на листе". Так она звучала в моей формулировке пару лет назад. Искал решение, но так и не нашёл.
Так что эта задача меня тоже очень интересует. =)

[Alec]

Что-то я смотрю на рисунок и не въеду... То-ли они пересекаются, то-ли они не все прямоугольники...То-ли у меня экран искажает...
Похоже тебя жестоко накалывают

[Хакер]

Угу. E и C же пересекаются.

[tyomitch]

Автору: точного решения, кроме полного перебора, не существует.
Приближённых алгоритмов сколько угодно, в т.ч. коммерческие.
Гугли 2d packing problem

[Ramzes]

Угу. E и C же пересекаются.

просто спешил, когда рисовал, но общий смысл должен быть понятен

[Хакер]

Стоп. А размеры прямоугольников ведь даны? Или только площади?

[iGrok]

Стоп. А размеры прямоугольников ведь даны? Или только площади?

У меня даны. Думаю, у него тоже. Иначе задача не имеет смысла.

[Ramzes]

Стоп. А размеры прямоугольников ведь даны? Или только площади?

только площадь

[iGrok]

только площадь

Даже соотношение сторон неизвестно? Т.е. высоту и ширину не вычислить никак?
А в чём тогда заключается определение размещения?

[Ramzes]

Форма особого значения не имеет, неплохо бы конечно, чтобы прямоугольники эти были максимально приближен к квадрату.

[Хакер]

Если даны только площади, то просто подели большой прямоугольник горизонтальными линиями на части, пропорциональные площадям.

Или фишка именно в квадратайзинге?

[Ramzes]

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