Упаковка прямоугольников

[monster-bonster]

Привет всем!
Вышла задача для которой никак не могу придумать структуру данных

Даны четыре прямоугольника, т.е. файл в котором есть четыре строки
в каждой строке два числа определяющие стороны прямоугольника.
Требуется упаковать их в один прямоугольник с минимальной площадью,
так чтобы прямоугольники не должны прикрывать друг друга. При упаковке
можно поворачить прямоугольники на 90 градусов.

Пример ввода данных

1 2
2 3
3 4
4 5

Пример вывода

4 10
5 8

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

Никак не могу найти для этого структуру данных
Пробовал так.

struct rectangle {
  int a, b;
};

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

[Serge_Bliznykov]

проблема в том, что Вам нужно думать над АЛГОРИТМОМ решения,
а Вы думаете над тем, как отобразить прямоугольники в программе (т.е. над второстепенными техническими деталями...
Думайте над алгоритмом.
(вот, представьте, вам дали 10 прямоугольников (из картона).
Как бы Вы находили варианты решения (просто, ручками, на столе, без компьютера)?...


p.s. я с налёта красивого алгоритма решения не вижу..
Очевидно, что полученный в результате не может иметь сторону, меньше, сумма сторон некоторых исходных прямоугольников..
Но другого варианта, как полный перебор всех возможных размещений я не вижу...

[monster-bonster]

Вы правы, но ведь прежде чем реализовать алгоритм перебора
вариантов, нужно организовать структуру данных, функции, которые
работают над ним (объединяют, поворачивают и т. д.). Алгоритм перебора
я реализую без проблем, но ведь как я сказал алгоритм не проблема, но
вот структура данных ни как не складывается.

[Abstraction]

Никак не могу найти для этого структуру данных
Пробовал так.

struct rectangle {
  int a, b;
};

Ну, так нормально, почему нет? Можно переделать в класс и привинтить метод flip()... а заодно square()... а заодно minimalSide(). Вот только объемлющий прямоугольник - это скорее сетка, её надо реализовывать более богатым типом.

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

[Granus]

Сообщение от Abstraction

Можно переделать в класс и привинтить метод

Структура - тоже класс, и у нее тоже есть методы)

monster-bonster, Abstraction прав, подумайте, добавьте необходимые методы и все будет отлично

[Serge_Bliznykov]

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

[Abstraction]

Структура - тоже класс, и у нее тоже есть методы)

Я бы сказал, что так делать можно, но не нужно. Есть удобное семантическое разделение: структура - тупое произведение составляющих типов, класс - некоторая дополнительная структура на этом произведении и/или инкапсуляция деталей. Даже если стандарт языка на нём не настаивает, всё равно имеет смысл его поддерживать.

[Granus]

Сообщение от Abstraction

Я бы сказал, что так делать можно, но не нужно. Есть удобное семантическое разделение: структура - тупое произведение составляющих типов, класс - некоторая дополнительная структура на этом произведении и/или инкапсуляция деталей. Даже если стандарт языка на нём не настаивает, всё равно имеет смысл его поддерживать.

Да, почти полностью согласен. Я бы сказал, что структуру семантически лучше использовать, если у типа тривиальный конструктор.

[monster-bonster]

Я бы рад использовать классы, но я должен
решить эту задачу на компиляторе gnu c.
Пожалуйста если это вас не затруднит, определите
решение более специфично, а то вы так поверхностно
объясняете.