凸多边形最优三角剖分（动态规划）

【问题描述】使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。

【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。

【输出形式】最优三角剖分后的三角形顶点。

【样例1输入】

7

8 26

0 20

0 10

10 0

22 12

27 21

15 26

【样例2输出】

012

234

024

456

046

【样例说明】

 输入：顶点个数为7，每一行为一个顶点坐标(x, y)，以空格分隔。

 输出：每一行为顺序产生的最优三角剖分后的三角形顶点。

#include
#include
using namespace std;

struct point {
double x;
double y;
};

double w(int a, int b, int c, point* p) {
double d1 = sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y));
double d2 = sqrt((p[a].x - p[c].x) * (p[a].x - p[c].x) + (p[a].y - p[c].y) * (p[a].y - p[c].y));
double d3 = sqrt((p[c].x - p[b].x) * (p[c].x - p[b].x) + (p[c].y - p[b].y) * (p[c].y - p[b].y));
return d1 + d2 + d3;
}

template
void MinWeight(int n, Type** t, int** s,point*p) {
for (auto i = 1; i <= n; i++)t[i][i] = 0;
for (auto r = 2; r <= n; r++) {//当前计算的链长
for (auto i = 1; i <= n - r + 1; i++) {//n-r+1为最后一个r链的前边界
int j = i + r - 1;//就算前边界为i,链长为r的链的后边界
t[i][j] = t[i + 1][j] + w(i - 1, i, j, p);//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i
s[i][j] = i;
for (int k = i + 1; k < i + r - 1; k++) {
//将链ij划分为( A[i:k] )* (A[k+1:j])
int u = t[i][k] + t[k + 1][j] + w(i - 1, k, j, p);
if (u < t[i][j]) {
t[i][j] = u;
s[i][j] = k;
}
}
}
}
}
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 << i - 1 << s[i][j] << j << endl;
}
int main()
{
int n;
cin >> n;
point* p = new point[n + 1];
for (auto i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y;
}
double** t = new double* [n + 1];
int** s = new int* [n + 1];
for(auto i = 0; i < n + 1; i++) {
t[i] = new double[n + 1];
s[i] = new int[n + 1];
}
MinWeight(n, t, s, p);
Traceback(1, n-1, s);
}

/*
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26

*/