Задачка для скучающих программистов.

[Спалланцани]

На мой нубский взгляд довольно трудная задачка.

На вход подается таблица с размерами прямоугольников. в формате L H длинна и высота.

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

То есть накладывая одни прямоугольники на другие найти такое наложение чтобы была минимальная площадь.

[napancux]

Может я чего-то не понимаю, но если прямоугольники накладывать друг на друга, то минимальная площадь будет достигаться, если совместить одни из углов (левый нижний, правый верхний, неважно) всех прямоугольников. И тогда бОльшие прямоугольники будут закрывать меньшие. Не?

[Спалланцани]

napancux, Поворачивать их еще можно.

[Enta]

napancux, Поворачивать их еще можно.

наркомания...
поставил бы хоть 50р для затравки...

а вообще первые 2 шага - совмещение крестом самого длинного и самого широкого (где ширина меньше длинны)

[napancux]

Спалланцани, у ты какой хитрый

[Спалланцани]

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

[explorer199]

Поворачиваем все прямоугольники "длинной" стороной по одной оси, совмещаем левую верхнюю вершину, обводим. Опровержение?

[LuSaa]

Если на 90 градусов поворачивать, то чушь какая-то, нет? Просто берешь самый большой, кладешь на него остальные и все?

[Darij]

To Спалланцани:

Условие задачи неполное. Есть два варианта интерпретации:

1. Проекции прямоугольников могут пересекаться. Пример - прямоугольники из бумаги складываются в стопку. Тогда при условии L<=H общая площадь стопки не может превышать (MAX(L))^2.

2. Проекции прямоугольников пересекаться не могут. Пример - складывание пустых коробок одна в другую. Тогда прямоугольник можно поместить в другой только при условии L1<=L2, H1<=H2. В таком случае общая площадь в худшем случае (ни одна коробка не помещается в другую) будет равна сумме площадей всех прямоугольников. В лучшем случае (все коробки матрешкой складываются одна в другую) общая площадь будет равна площади самого большого прямоугольника.

[Enta]

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

0. повернуть так чтоб длинна была больше ширины.
1. отсортировать по длинне
2. S = S1 + ... Sn
S1 = A1*B1, Sn=An*(Bn-B(n-1)) при Bn>B(n-1) иначе Sn=0

[napancux]

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

[Спалланцани]

explorer199, Напиши)

[LuSaa]

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

Ну вон, ребята уже нписали верное решение. Все равно задача слишком простая. Что-то тут не так.

[explorer199]

explorer199, Напиши)

Программу? Тогда спецификацию ввода-вывода, чтобы потом не было споров по этому поводу.

[Спалланцани]

Darij, Да могут пересекаться.

- - - Добавлено - - -

explorer199, Таблица прямоугольников. длинна ширина перенос строки. Конец файла в конце. На выходе площадь.

[cScDes]

0. повернуть так чтоб длинна была больше ширины.
1. отсортировать по длинне
2. S = S1 + ... Sn
S1 = A1*B1, Sn=An*(Bn-B(n-1)) при Bn>B(n-1) иначе Sn=0

Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.

[napancux]

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

Ну так-то уже сказали.

А я вот тут подумал, если поворачивать можно как угодно.

1) Помещаем первый прямоугольник на условную плоскость;
2) Помещаем следующий прямоугольник массива в центр первого;
3) Сравниваем стороны, если (H2 && L2) > (H1 && L1) || (H2 && L2) < (H1 && L1), то ничего не делаем, так как прямоугольники покрывают друг друга;
4) Далее, если H2 > H1 || L2 > L1, то поворачиваем новый прямоугольник таким образом, чтобы его центральная ось совпадала с диагональю уже помещенного прямоугольника, а центры прямоугольников совпадали;
5) Все "повернутые" прямоугольники держим в переменной;
6) Если появляется бОльший прямоугольник, то соответственно совмещаем все повернутые прямоугольники с новой диагональю.

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

[Enta]

Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.

согласен.
итого:
0. повернуть так чтоб длинна была больше ширины.
1. отсортировать по длинне
2. S = S1 + ... Sn
S1 = A1*B1, Sn=An*(Bn-MAX(B1 .. B(n-1))) при Bn>Bn-MAX(B1 .. B(n-1)) иначе Sn=0

Был бы трезвее, написал бы SQL запрос...

[napancux]

Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.

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

[explorer199]

А, я думал, что нужно найти площадь прямоугольника, обводящего все эти прямоугольники
Сами пишите, мне лень.