凸多边形最优三角剖分.cpp

动态规划解一系列经典问题

//凸多边形最优三角剖分

#include <iostream.h>
#include <math.h>
#include <iomanip.h>
#define N 6
double a[][2]={{1,0},{3,0},{2,3},{0,3},{1,4},{0,2}};
int t[N][N]={0},s[N][N]={0};

void Output(int n, int x[N][N])
{
	for(int i=1; i<n-1; i++)
	{
		cout<<endl<<setw(8*i-7)<<0;
		for(int j=i+1; j<n; j++)
			cout<<'\t'<<x[i][j];
	}
	cout<<endl<<setw(8*i-7)<<0<<endl;
}

int w(int x, int y, int z)
{
	double s1=abs(a[x][0]-a[y][0]),s2=abs(a[x][1]-a[y][1]);
	double s=sqrt(s1*s1+s2*s2);
	s1=abs(a[x][0]-a[z][0]),abs(s2=a[x][1]-a[z][1]);
	s+=sqrt(s1*s1+s2*s2);
	s1=abs(a[y][0]-a[z][0]),abs(s2=a[y][1]-a[z][1]);
	s+=sqrt(s1*s1+s2*s2);
	return (int)s;
}

void MinWeightTriangulation(int n)
{
	for(int r=2; r<n; r++)
	{
		for(int i=1; i<=n-r; i++)
		{
			int j=i+r-1;
			t[i][j]=t[i+1][j]+w(i-1,i,j);
			s[i][j]=i;
			for(int k=i+1; k<j; k++)
			{
				double u=t[i][k]+t[k+1][j]+w(i-1,k,j);
				if (u<t[i][j])
				{
					t[i][j]=u;
					s[i][j]=k;
				}
			}
		}
	}
}

void Traceback(int i, int j)
{
	if (i==j) return;
	Traceback(i, s[i][j]);
	cout<<"△A"<<i<<"-A"<<s[i][j]+1<<"-A"<<j+1<<endl;
	Traceback(s[i][j]+1, j);
}

void main()
{
	MinWeightTriangulation(N);
	Output(N, t);
	Output(N, s);
	Traceback(1,N-1);
	cout<<endl;
}