Описание
На плоскости отмечено N=3K точек. Будем рассматривать такие варианты построения К невырожденных треугольников с вершинами в этих точках, при которых каждая из заданных точек является вершиной какого-либо треугольника. Точки расположены так, что хотя бы одно построение с указанным свойством существует

Задание
Требуется определить тот вариант, при котором суммарная площадь полученных К треугольников минимальна


Входные данные
Во входном файле содержатся (в указанном порядке) целое число N (1N30) и N пар вещественных чисел, задающих координаты точек. Числа разделяются пробелами и/или символами перевода строки

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


Например:

TRIANGLE.IN
6
0 0
1 0
10 0
0 2
12 0
10 1

TRIANGLE.OUT
2
1 2 4
3 5 6




Идеи
Перебор с отсечениями, площадь треугольника

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

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

Как можно улучшить это отсечение? Заметим, что, сравнивая общую площадь треугольников с min, мы никак не учитываем количество треугольников, которые осталось построить. Это можно сделать так. Перед началом работы переборного алгоритма вычислим площадь минимального треугольника, который возможно построить, взяв в качестве вершин какие-то три из заданных N точек (Smin). Если на очередном шаге перебора нам осталось построить r треугольников, a S+r·Smin min, то также следует выполнить отсечение

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

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

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



Решение

{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+} 
{$M 65520,0,655360} 
 
program triangle; 
const Delta=0.000001; 
      MaxN=10; 
type real = extended; 
     Point=record 
       x,y:real 
     end; 
 
var a:array[1..3*MaxN] of Point; 
    a_:array[1..3*MaxN] of record 
                             x,y:integer 
                           end; 
    MinT,Tr:array[1..MaxN,1..3] of integer; 
    MinS:array[1..3*MaxN] of real; 
    Was:array[1..3*MaxN] of boolean; 
    i,j,k,n:integer; 
    min,MinTr:real; 
    time : longint absolute $0000:$046C; 
    breakTime : longint; 
 
Procedure Input_; 
Var i:integer; 
Begin 
  Assign(input,'triangle.in'); 
  Reset(input); 
 
  read(n); 
  for i:=1 to n do 
    read(a[i].x,a[i].y) 
End(*Input*); 
 
Procedure MashTab; 
Var i:integer; 
    MinX,MinY,MaxX,MaxY,kX,kY:real; 
 
Begin 
  MinX:=1e28; MinY:=1e28; MaxX:=-1e28; MaxY:=-1e28; 
 
  for i:=1 to n do begin 
    if a[i].x then MinX:=a[i].x; 
    if a[i].y then MinY:=a[i].y; 
    if a[i].x>MaxX then MaxX:=a[i].x; 
    if a[i].y>MaxY then MaxY:=a[i].y 
  end; 
 
  MinX:=MinX-3; MinY:=MinY-3; 
  kX:=(639-2)/(MaxX-MinX); 
  kY:=(339-2)/(MaxY-MinY); 
 
  for i:=1 to n do begin 
    a_[i].x:=round((a[i].x-MinX)*kX); 
    a_[i].y:=round((a[i].y-MinY)*kY) 
  end 
End(*Mashtab*); 
 
Function Sq(i,j,k:integer):real; 
Var r:real; 
Begin 
  r:=abs( a[i].x*(a[k].y-a[j].y)+a[j].x*(a[i].y-a[k].y)+ 
          a[k].x*(a[j].y-a[i].y) ); 
  if r then r:=0; 
  Sq:=r 
End(*Sq*); 
 
Procedure Zgad; 
Var p,i,j,k:integer; 
    mn:set of 1..3*MaxN; 
    r,q,m:real; 
Begin 
  mn:=[1..n]; 
  Min:=0; 
 
  for p:=1 to n div 3 do begin 
    q:=1e28; m:=1e20; 
    for i:=1 to n-2 do 
      if i in mn then 
      for j:=i+1 to n-1 do 
        if j in mn then 
        for k:=j+1 to n do 
          if (k in mn) then begin 
            r:=Sq(i,j,k); 
            if (r<>0) and (r then begin 
              MinT[p,1]:=i; MinT[p,2]:=j; MinT[p,3]:=k; 
              m:=r 
            end 
          end; 
    mn:=mn-[MinT[p,1]]-[MinT[p,2]]-[MinT[p,3]]; 
    Min:=Min+m 
  end 
End (*Zgad*); 
 
Procedure Local; 
Const L:array[1..3] of record 
                         a,b:byte 
                       end 
                     = ((a:2;b:3),(a:1;b:3),(a:2;b:1)); 
Var i,j,p,t,r:integer; 
    Min_,a,b:real; 
    Label _; 
Begin 
_: 
  for i:=1 to n div 3-1 do 
    for k:=i+1 to n div 3 do begin 
      Min_:=Min-Sq(MinT[i,1],MinT[i,2],MinT[i,3])- 
                Sq(MinT[k,1],MinT[k,2],MinT[k,3]); 
 
      for p:=1 to 3 do 
        for t:=1 to 3 do begin 
          a:=Sq(MinT[i,L[p].a],MinT[i,L[p].b],MinT[k,t]); 
          b:=Sq(MinT[k,L[t].a],MinT[k,L[t].b],MinT[i,p]); 
          if (a*b<>0) and (Min_+a+b then begin 
            r:=MinT[i,p]; 
            MinT[i,p]:=MinT[k,t]; 
            MinT[k,t]:=r; 
            Min:=Min_+a+b; 
            Goto _ 
          end 
        end 
     end; 
End(*Local*); 
 
Procedure Per(t,k:integer;sum:real); 
Var i,j:integer; 
Begin 
  if time > breakTime then exit; 
  if (t div 3) and (Sum+MinS[t]+MinTr*(n-3*t-3)>=Min) or (Sum>=Min) 
    then Exit; 
  if t>n div 3 then begin 
    MinT:=Tr; 
    Min:=Sum; 
    Local; 
    Exit 
  end; 
 
  while not Was[k] do inc(k); 

  Tr[t,1]:=k; Was[k]:=false; 
  for i:=k+1 to N-1 do 
    if Was[i] then 
      for j:=i+1 to N do 
        if Was[j] and (Sq(i,j,k)<>0) then begin 
          Tr[t,2]:=i; Tr[t,3]:=j; 
          Was[i]:=false; Was[j]:=false; 
          Per(t+1,k+1,Sum+Sq(i,j,k)); 
          Was[i]:=true; Was[j]:=true 
    end; 
  Was[k]:=true 
End (*Per*); 
 
procedure outAnswer; 
var 
  i, j : integer; 
begin 
  assign(output, 'triangle.out'); 
  reWrite(output); 
  writeLn(Min/2); 
  for i := 1 to n div 3 do 
    writeLn(MinT[i,1], ' ', MinT[i,2], ' ', MinT[i,3]); 
end; 
 
BEGIN 
  breakTime := time + Round(15/55*1000)-3; 
  Input_; 
  Mashtab; 
 
  for k:=1 to n do begin 
    MinS[k]:=1e20; 
    for i:=1 to n-1 do 
      for j:=i+1 to n do begin 
        min:=Sq(i,j,k); 
        if (min<>0) and (min then 
          MinS[k]:=min 
      end 
  end; 
 
  MinTr:=1e28; 
  for i:=1 to n do 
    if MinS[i] then MinTr:=MinS[i]; 
 
  Zgad; 
  if Min<1e20 then Local; 
  FillChar(Was,SizeOf(Was),$FF); 
  Per(1,1,0); 
  OutAnswer; 
 
  close(input);close(output) 
END. 



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

TRIANGLE.OUT
 2.00000000000000E+0000
1 2 4
3 5 6

© Особенности национальных задач по информатике