help!!!!!!!!!
查看原帖
help!!!!!!!!!
776799
GODTREE楼主2023/3/23 13:54

为什么过不了???

#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;
}
2023/3/23 13:54
加载中...