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

[Darij]

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

Тогда так:
На входе массив из 2 полей - L и H.
Предварительный прогон - если H>L, меняем их местами ("поворачиваем на 90 градусов")

1. Сортируем массив по L (по убыванию) и Н(по возрастанию)
2. Базовая площадь: S = L1*H1 (самый длинный прямоугольник)
3. Сохраняем значение H1 в переменную H_Current
4. Далее цикл по массиву со второй строки:
Если H(i) <= H_Current, игнорируем прямоугольник, переход к следующему (он полностью закрыт предыдущим)
иначе увеличиваем площадь S на площадь выступающего куска (S = S + (H(i) - H_Current)*L(i)) и присваиваем новое значение H_Current = H(i)
5. Цикл закончен, результат в переменной S.

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

Ну хорошо раз вы такие уверенные и крутые. То пусть омжно будет поворачивать ан любой угол.

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

Darij, Площадь считается не правильно.

[Darij]

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

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

[napancux]

С заданной заранее таблицей и сортировкой - неочень У Darij все верно, вроде как.

[Enta]

Ну хорошо раз вы такие уверенные и крутые. То пусть омжно будет поворачивать ан любой угол.

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

завтра может быть посмотрю.

[cScDes]

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

так ты сортируй по убыванию длины и будут только прямоугольники.

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

Darij,

Вот так может быть.

[Федор Сумкин]

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

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

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

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

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

[napancux]

Спалланцани, а что ты скажешь насчет моей догадки на первой странице?

[Darij]

Darij,

Вот так может быть.

Да, так может быть. Тогда нужно прогнать первый вариант, чтобы отбросить тривиальные случаи (обе координаты прямоугольника меньше другого) - а дальше нужно центрировать все прямоугольники и поворачивать по диагонали предыдущего. А вот посчитать в таком случае площадь пересечения - задача муторная, с разбиением на треугольники по точкам пересечения. Это больше из области прикладной геометрии или компьютерной графики.. Решение будет лишено какого-либо изящества.

P. S. Почему ты считаешь мой расчет площади неправильным? Там все корректно..

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

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

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

[Ameno_64]

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

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

А разве в обоих случаях это не классическая NP полная задача коммивояжера/рюкзака ?

[yaCooler]

Странная задача. Было бы интереснее попробовать разместить их так, чтобы они не пересекались и чтобы площадь описываемой окружности была наименьшей. А так - сортируем по площади и лепим все в центр самого большого, попутно поворачивая каждый вдоль наибольшей его диагонали в случае, когда площадь выступающих за края самого большого остатков превышает площади 4х фигур, образуемых остатками повёрнутой фигуры...

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

yaCooler, Описанная тобой задача не имеет 1 алгоритма решения.

[yaCooler]

yaCooler, Описанная тобой задача не имеет 1 алгоритма решения.

Которая из? Которая с окружностью? или которая с площадями фигур?

[Darij]

А разве в обоих случаях это не классическая NP полная задача коммивояжера/рюкзака ?

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

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

P.S. Второй вариант тоже не является "задачей коммивояжера". Наиболее близкий аналог из комбинаторной оптимизации - "задача раскроя".

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



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

[Centrin0]

Это же задача про заказчика: угадай какие условия задачи на самом деле и сдай заказчику проект

[napancux]

Darij, а высота коробки в данном случае зачем?

[Darij]

Darij, а высота коробки в данном случае зачем?

Чтобы задача была приближена к реальности, добавляем третье измерение. Ну и усложняем тем самым задачу, давая возможность ставить коробки вдоль, поперек и вертикально, поворачивая их при этом как удобно. А картинка иллюстрирует 2D вариант задачи (в 3D слишком долго пришлось бы рисовать).

[qowner]

Не кормите ленивых студентов. Задачка (исходная) элементарная, даже не олимпиадная. Лаба на знание массивов.

[KoptecW]

Еще не плохо было бы написать алгоритм для задачи: исходное пространство ограничено, прямоугольники/параллелепипеды не могут пересекаться, найти идеальное расположение их на плоскости (или в 3х мерном пространстве). Что-то вроде того, как разместить вещи в багажнике. Она же задача "оптимального раскроя".