Optimal polygon triangulation using Dynamic programming(DP) with memoization.

DP_Triangulation.cpp

#include <iostream>
#include <algorithm>
using namespace std;
int N;
double px[100];
double py[100];
double DP[100][100];
int backtrack[100][100];
double dist(int from, int to)
{
    if(from + 1 == to) return 0;
    double x, y;
    x = abs(px[from] - px[to]);
    y = abs(py[from] - py[to]);
    return sqrt(x*x + y*y);
}
double rec(int from, int to)
{
    if(from + 2 >= to) return 0;
    if(DP[from][to] != -1) return DP[from][to];
    double optimal = 1 << 29;
    for(int i = from + 1; i < to; ++i)
    {
        double current = dist(from, i) + dist(to, i) + rec(from, i) + rec(i, to);
        if(optimal > current)
        {
            optimal = current;
            backtrack[from][to] = i;
        }
    }
    DP[from][to] = optimal;
    return optimal;
}
void print(int from, int to)
{
    if(backtrack[from][to] == 0) return;
    if(from + 1 < backtrack[from][to]) cout<<"Diagonal "<<from<<"-"<<backtrack[from][to]<<endl;
    if(backtrack[from][to] + 1 < to) cout<<"Diagonal "<<backtrack[from][to]<<"-"<<to<<endl;
    //cout<<"Making a cut between points "<<from<<" and "<<to<<" in point "<<backtrack[from][to]<<endl;
    print(from, backtrack[from][to]);
    print(backtrack[from][to], to);
}
int main()
{
    cin >> N;
    for(int i = 1; i <= N; ++i)
    {
        double x, y;
        cin >> x >> y;
        px[i] = x;
        py[i] = y;
    }
    fill(&DP[0][0], &DP[0][0] + 100*100, -1);
    double result = rec(1, N);
    print(1, N);
    cout<<"Minimum value: "<<result<<endl;
    return 0;
}
/*
5
0 0
1 0
2 1
1 2
0 1
*/