为什么过不了???
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const double INF = 1e20;
int n;
int x[N], y[N];
double dp[N][N];
// 计算三角形面积
double triangle_area(int x1, int y1, int x2, int y2, int x3, int y3)
{
return fabs((x1-x3)*(y2-y3) - (x2-x3)*(y1-y3)) / 2.0;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &x[i], &y[i]);
// dp[i][j] 表示将 i 到 j 区间剖分成三角形后最大的三角形面积最小是多少
memset(dp, 0, sizeof(dp));
// 初始化 dp 数组
for (int i = 0; i < n; i++)
dp[i][(i+1)%n] = 0;
// 区间 DP
for (int len = 3; len <= n; len++)
{
for (int i = 0; i < n; i++)
{
int j = (i + len - 1) % n;
for (int k = (i+1)%n; k != j; k = (k+1)%n)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + triangle_area(x[i], y[i], x[k], y[k], x[j], y[j]));
}
}
// 输出结果
printf("%.2lf\n", dp[0][n-1]);
return 0;
}