Треугольники

На плоскости отмечено 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 приходится полагать равным бесконечности, и нет никакой гарантии, что первые из построенных решений будут настолько хорошими, чтобы указанное отсечение работало эффективно (а это попросту необходимо). Следовательно, нужно каким-то образом подобрать хорошее начальное решение. Это можно сделать, например, с помощью жадного алгоритма: строим треугольник с минимально возможной площадью, выкидываем его вершины, строим треугольник с минимальной площадью из оставшихся точек и т. д. 

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