Задача №17

Написать программу по оптимальному раскрою листа заданных размеров на заданные детали.

 

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

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

Все размеры и координаты в этой задаче - целые числа.

Входной файл устроен так:
1) первая строка - ширина полосы (не более 100),
2) вторая строка - количество типов фигур (не более 100),
3) с третьей по последнюю строчку - описание фигуры.
Описание фигуры - это строка, состоящая из целого числа (количества экземпляров фигуры, которые надо разместить на полосе) и серии пар целых чисел (координат вершин) - не более 100 вершин в одной фигуре.

Пример входного файла:

3
2
8 0 0 0 1 2 1 2 0
4 0 0 0 1 1 0

(в этой задаче мы имеем полосу ширины 3, на которой надо расположить 8 фигурок домино (прямоугольников 2х1) и 4 равнобедренных прямоугольных треугольника с катетом 1.

 

Ответом программы должны быть строки (ровно столько, сколько всего фигур), содержащие четыре числа: номер типа фигуры (целое число), координаты первой вершины фигуры (возможно использование вещественных чисел) и угол поворота против часовой стрелки в градусах (целое число).

 

Пример ответа (для представленных выше входных данных теоретический минимум полосы, вычисленный делением суммарной площади фигур на ширину полосы, достижим, но это бывает далеко не всегда):

1 0 0 0
1 0 3 270
1 1 3 270
1 2 0 0
1 2 3 270
1 3 3 270
1 4 3 270
1 5 3 270
2 4 0 0
2 5 1 180
2 5 0 0
2 6 1 180

 

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

Картинки и ролики по теме этой задачи (nesting) можно посмотреть здесь: http://tehtran.com/nestf.html 

 

YouTube: