#include <iostream>  
#include<math.h>
using namespace std;   
#define MAXSIZE 100  
 
 double Weight(int a,int b,int c);
struct
{
    int x;
    int y;
}v[MAXSIZE];
int main()
{
    double m[MAXSIZE][MAXSIZE];
    int s[MAXSIZE][MAXSIZE],i,n;
    cout<<"输入多边形顶点个数n：\n";
    cin>>n;
    cout<<"输入顶点坐标：\n";
    for(i=1;i<=n;i++)
    {   cout<<"输入第"<<i<<"个顶点的坐标\n";
        cin>>v[i].x>>v[i].y;
    }
   
    for(int i=1;i<=n;i++)
        m[i][i]=0;
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            m[i][j]=m[i+1][j]+Weight(i-1,i,j);
            s[i][j]=i;
            for(int k=i+1;k<j;k++)
            {
                double q=m[i][k]+m[k+1][j]+Weight(i-1,k,j);
                if(q<m[i][j])
                    {
                        m[i][j]=q;
                        s[i][j]=k;
                    }
            }
        }
    }
   
    cout<<"此多边形的最优三角划分结构为："<<endl;
    Traceback(1,n,s);
    cout<<"此多边形的最优三角划分值为："<<m[1][n-1]<<endl;
    system("pause");
   
    return 0;
}



double Weight(int a,int b,int c)
{   double w1,w2;
    if(a+1==b)
         w1=0;
    else
         w1=sqrt((v[b].x-v[a].x)*(v[b].x-v[a].x)+(v[b].y-v[a].y)*(v[b].y-v[a].y));
    if(b+1==c)
         w2=0;
    else
         w2=sqrt((v[c].x-v[b].x)*(v[c].x-v[b].x)+(v[c].y-v[b].y)*(v[c].y-v[b].y));
    return w1+w2;
}

void Traceback(int i,int j,int *s)  
{  
    if(i==j) return;  
    Traceback(i,s[i][j],s);  
    Traceback(s[i][j]+1,j,s);  
    cout<<"三角剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl;  
}