#include <iostream>
#include <cmath>
#define MAX 1000000.0
using namespace std;

// Structure of a point in 2D plane
struct Point
{
    int x, y;
};

// Нахождение минимума двух значений
double min(double x, double y)
{
    return (x <= y)? x : y;
}

// Евклидово расстояние
double dist(Point p1, Point p2)
{
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) +
                (p1.y - p2.y)*(p1.y - p2.y));
}

 double GetMinCost(Point points[], int i, int j, int n, double **table) {
     //cout << i << " " << j << " " << endl;
   if (table[i][j] != -1)
     return table[i][j];//рекурсия

     if ( (i + 1) % n == j ) {
         table[i][j] = 0;
         return table[i][j]; //мемоизация
     }
     return 0;
 }
// рассчёт стоимости
double cost(Point points[], int i, int j, int k)
{
    Point p1 = points[i], p2 = points[j], p3 = points[k];
    return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);
}

//наилучшая стоимость
double mTCDP(Point points[], int n)
{
   // Условие многоугольника!
   if (n < 3)
      return 0;


   double table[n][n];
 //Сохранение результатов.В массив[i][j] сохраняю стоимость от точек i до j
    //таблица [0][n-1] - массив окончательных результатов!

   for (int gap = 0; gap < n; gap++)
   {
      for (int i = 0, j = gap; j < n; i++, j++)
      {
          if (j < i+2)
             table[i][j] = 0.0;
          else
          {
              table[i][j] = MAX;
              for (int k = i+1; k < j; k++)
              {
                double val = table[i][k] + table[k][j] + cost(points,i,j,k);
                if (table[i][j] > val)
                     table[i][j] = val;
              }
          }
      }
   }
   return  table[0][n-1];
}

// Проверка вышеуказанных условий
int main()
{
    Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
    int n = sizeof(points)/sizeof(points[0]);
     double **table = (double**)malloc(sizeof(double) * n); //сохрание значений и деление на подзадачи
      for (int i = 0; i < n; i++) {
        table[i] = (double*)malloc(sizeof(double) * n);
        for (int j = 0; j < n; j++) {
          table[i][j] = -1;
        }
      }

      cout << GetMinCost(points, 0, n - 1, n, table) << endl;
      for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
          cout << table[i][j] << "  " << endl;
        }
      }
      for (int i = 0; i < n; i++) {
        free(table[i]);
      }
      free(table);

    cout << mTCDP(points, n)<<endl;
    return 0;
}