C++实现7-57 凸多边形最优三角剖分 分数 10 作者 严华云 单位 湖州师范学院 用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。 1.png 给定凸多边形P，用互不相交的弦将P分为一个个的三角形,称为凸多边形三角剖分。 然后，定义多边形的边和弦组成的三角形上的权w（本题定义三角形的权为边长之和）。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小，则称其为凸多边形P的最优三角剖分。 输入格式: 第一行一个n,表示有n个顶点（n<20）。 接下来n行，每行两个小数，分别表示该点的横坐标和纵坐标。 输出格式: 一个小数，表示最优三角剖分后，所有三角形的边长和的和最小值，小数点后保留2位。

这是一个经典的动态规划问题。设dp[i][j]表示将顶点i~j之间的多边形进行三角剖分所能得到的最小权值和，状态转移方程为：

dp[i][j] = min(dp[i][k]+dp[k][j]+w[i][j])

其中，k表示[i,j]区间内的任意一个顶点，w[i][j]表示从顶点i到顶点j之间的边的长度之和。如果[i,j]区间内只有两个顶点，则dp[i][j]为0，因为此时不需要进行三角剖分。

最终的结果为dp[0][n-1]，表示将整个多边形进行三角剖分所能得到的最小权值和。

下面是C++的参考代码实现：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 20;
const double eps = 1e-8;
double x[N], y[N], w[N][N];
double dp[N][N];

double calc(int a, int b, int c)
{
    double p = (w[a][b] + w[b][c] + w[c][a]) / 2;
    return sqrt(p * (p - w[a][b]) * (p - w[b][c]) * (p - w[c][a]));
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            w[i][j] = w[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));

    for (int len = 3; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++)
        {
            int j = i + len - 1;
            dp[i][j] = 1e20;
            for (int k = i+1; k < j; k++)
            {
                double area = calc(i, k, j);
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+area);
            }
        }

    printf("%.2lf\n", dp[0][n-1]);

    return 0;
}

其中，使用dp[i][j]表示将顶点i~j之间的多边形进行三角剖分所能得到的最小权值和。对于状态转移方程，需要特别注意循环的顺序，需要先枚举区间长度len，再枚举区间左端点i，最后计算右端点j和中间点k的位置。

另外，计算三角形的面积可以使用海伦公式，需要注意精度问题。