/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P11ConvexPolygonMinimalTriangulation {

  private static final String FileInputName = "triang.in";
  private static final String FileOutputName = "triang.out";
  private List<Point> vP;
  private List<Double> w;
  private double c[][];

  private static class Point {
    double first;

    double second;

    Point(double first, double second) {
      this.first = first;
      this.second = second;
    }

    double dist(Point p) {
      return Math.sqrt(Math.pow(this.first - p.first, 2)
          + Math.pow(this.second - p.second, 2));
    }
  }

  static double perimeter(Point p1, Point p2, Point p3) {
    return p1.dist(p2) + p2.dist(p3) + p3.dist(p1);
  }

  P11ConvexPolygonMinimalTriangulation(List<Point> vPoints) {
    this.vP = vPoints;
    this.w = new ArrayList<Double>();
    int szVP = vP.size();
    for (int i = 0; i < szVP - 2; i++)
      for (int j = i + 1; j < szVP - 1; j++)
        for (int k = j + 1; k < szVP; k++) {
          this.w.add(perimeter(vP.get(i), vP.get(j), vP.get(k)));
        }
    this.c = new double[szVP][szVP];
  }

  private double getW(int i0, int j0, int k0) {
    int n = this.vP.size();
    int p = 0;
    for (int i = 0; i < i0; i++) {
      p += (n - i - 1) * (n - i - 2) / 2;
    }
    for (int j = i0 + 1; j < j0; j++) {
      p += n - j - 1;
    }
    p += k0 - j0 - 1;
    return w.get(p);
  }

  void doProcess() {
    int szVP = this.vP.size();
    for (int p = 1; p < szVP; p++) {
      for (int i = 0; i < szVP - p; i++) {
        int k = i + p;
        if (1 == p)
          c[i][k] = 0;
        else {
          int j = i + 1;
          c[i][k] = c[i][j] + c[j][k] + getW(i, j, k);
          c[k][i] = j;
          for (j = i + 2; j < k; j++) {
            double val = c[i][j] + c[j][k] + getW(i, j, k);
            if (val < c[i][k]) {
              c[i][k] = val;
              c[k][i] = j;
            }
          }
        }
      }
    }
  }

  private void writeTriang(PrintStream out, int i, int j) {
    if ((j - i) > 1) {
      int k = (int) c[j][i];
      out.printf("  %d %d %d%n", i, k, j);
      writeTriang(out, i, k);
      writeTriang(out, k, j);
    }
  }

  void write(PrintStream out) {
    int idx = vP.size() - 1;
    out.printf(Locale.ENGLISH,
        " Kleinste Umfangssumme = %.4f%n bei Triangulierung: %n", c[0][idx]);

    writeTriang(out, 0, idx);
  }

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName));
      List<Point> vPoints = new ArrayList<Point>();
      while (scanner.hasNextDouble()) {
        double x = scanner.nextDouble();
        if (!scanner.hasNextDouble())
          break;
        double y = scanner.nextDouble();
        vPoints.add(new Point(x, y));
      }
      P11ConvexPolygonMinimalTriangulation p10 = 
                                new P11ConvexPolygonMinimalTriangulation(
          vPoints);
      p10.doProcess();
      out = new PrintStream(new File(FileOutputName));
      p10.write(out);
    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}