|
Название задачи: Треугольники . |
 |
Условие
На плоскости отмечено N = 3K точек. Будем рассматривать такие варианты построения K невырожденных треугольников с вершинами в этих точках, при которых каждая из заданных точек является вершиной какого-либо треугольника. Точки расположены так, что хотя бы одно построение с указанным свойством существует. Требуется определить тот вариант, при котором суммарная площадь полученных K треугольников минимальна.Входные данные
Во входном файле содержатся (в указанном порядке) целое число N (1 ≤ N ≤ 30) и N пар вещественных чисел, задающих координаты точек. Числа разделяются пробелами и/или символами перевода строки.
Выходные данные
Первая строка выходного файла должна содержать минимально возможное значение суммарной площади. В каждую из следующих K строк запишите тройку номеров вершин, образующих очередной из треугольников. Номера вершин разделяются пробелом.
Пример входного файла
6
0 0
1 0
10 0
0 2
12 0
10 1
Пример выходного файла
2
1 2 4
3 5 6
Решение
Скачать архив тестов и решенийРешением в данной задаче является любое из разбиений заданных точек на K треугольников, удовлетворяющее указанному в условии задачи требованию. На каждом шаге выбираем еще «не занятую» точку с наименьшим номером и пытаемся построить треугольник, имеющий ее своей вершиной. Для того, чтобы не анализировать одну и ту же ситуацию несколько раз, будем требовать, чтобы номера двух других вершин треугольника следовали в порядке возрастания.
В процессе перебора храним общую площадь построенных к данному моменту треугольников (S) и суммарную площадь в наилучшем из ранее найденных построений (min). Простейшее из отсечений, которое мы можем использовать, состоит в следующем. Если на каком-то шаге окажется, что S ≥ min, то продолжать построение не имеет смысла и необходимо вернуться к предыдущему шагу.
Как можно улучшить это отсечение? Заметим, что, сравнивая общую площадь треугольников с min, мы никак не учитываем количество треугольников, которые осталось построить. Это можно сделать так. Перед началом работы переборного алгоритма вычислим площадь минимального треугольника, который возможно построить, взяв в качестве вершин какие-то три из заданных N точек (Smin ). Если на очередном шаге перебора нам осталось построить r треугольников, а S + r·Smin ≥ Smin, то также следует выполнить отсечение.
Полученный алгоритм имеет следующий недостаток. В начальный момент
времени min приходится полагать равным бесконечности, и нет никакой
гарантии, что первые из построенных решений будут настолько хорошими,
чтобы указанное отсечение работало эффективно (а это попросту необходимо).
Следовательно, нужно каким-то образом подобрать хорошее начальное
решение. Это можно сделать, например, с помощью жадного алгоритма: строим
треугольник с минимально возможной площадью, выкидываем его вершины,
строим треугольник с минимальной площадью из оставшихся точек и т. д.
Для дальнейшего улучшения алгоритма применим метод локальной оптимизации. Пусть отыскалось решение с меньшей суммарной площадью, чем наилучшее из ранее найденных. Попробуем обменять вершины у каких-то двух треугольников, т.е. перейти от левого рисунка к правому. Перебрав все пары построенных треугольников и все варианты обмена вершин внутри них, нам с некоторой вероятностью удастся улучшить рассматриваемое решение.
