给出凸多边形的每个点的坐标怎么求凸多边形最优三角剖分

凸多边形的最优三角剖分可以通过动态规划来求解。具体步骤如下：

1. 定义状态：设 $dp[i][j]$ 表示将多边形从第 $i$ 个点到第 $j$ 个点之间进行三角剖分所得到的最小值。

2. 状态转移方程：对于任意的 $i < k < j$，假设将多边形从第 $i$ 个点到第 $j$ 个点之间的某个点 $k$ 进行三角剖分，得到的两个三角形的面积分别为 $S_1$ 和 $S_2$，则有：

$$dp[i][j] = \min_{i<k<j} \{dp[i][k] + dp[k][j] + S_1 + S_2\}$$

其中 $S_1$ 和 $S_2$ 可以通过向量叉积来计算，即：

$$S_1 = \frac{1}{2} \times ((x_k - x_i)(y_j - y_i) - (x_j - x_i)(y_k - y_i))$$

$$S_2 = \frac{1}{2} \times ((x_k - x_j)(y_i - y_j) - (x_i - x_j)(y_k - y_j))$$

3. 初始化：当 $j = i+1$ 时，$dp[i][j] = 0$。

4. 最终答案：$dp[1][n]$，其中 $n$ 为多边形的顶点数。

时间复杂度为 $O(n^3)$。