uva 1331——Minimax Triangulation

╰+哭是因爲堅強的太久メ 2022-08-18 02:42 123阅读 0赞

题意：三角刨分，把一个m边形分解成m-2个三角形，求一个最大三角形最小的刨分，输出最小的那个三角形面积。

思路：递推。可能需要一点几何思维，d（i，j）为多边形的最优解，则d（i，j）=min（s（i，j，k），d（i，k），d（k，j））；s（i，j，k）是三角形i-j-k的面积。然后枚举i，j，k求出最优即可。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    #define ft(i,s,t) for (int i=s;i<=t;i++)
    const int INF=0x3f3f3f3f;
    const int N=55;
    const double ep=1e-6;
    struct node
    {
    	double x,y;
    }v[N];
    int n;
    double dp[N][N];
    double area (node A,node B,node C)
    {
    	return 0.5*fabs((B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y));
    }
    
    int ok(int a,int b,int c)
    {
    	double t=area(v[a],v[b],v[c]);
    	ft(i,0,n-1)
    	{
    		if (i==a||i==b||i==c) continue;
    		double sum=(area(v[a],v[b],v[i])+area(v[a],v[i],v[c])+area(v[i],v[b],v[c]));
    		if (fabs(sum-t)<ep) return 0;
    	}
    	return 1;
    }
    double sol()
    {
    	double ans=INF;
    	ft(i,2,n-1) ft(j,0,n-1)
    	{
    	    int r=(i+j)%n;
    	    dp[j][r]=INF;
    	    for(int k=(j+1)%n;k!=r;k=(k+1)%n){
                if (ok(j,k,r))
                    dp[j][r]=min(dp[j][r],max(max(dp[j][k],dp[k][r]),area(v[j],v[k],v[r])));
    	    }
    	    if (i==n-1)
                ans=min(ans,dp[j][r]);
    	}
    	return ans;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		ft(i,0,n-1) scanf("%lf %lf",&v[i].x,&v[i].y);
    		printf("%.1f\n",sol());
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 Minimax 算法中的 Alpha Beta 剪枝

就像我们在之前的文章中讨论的那样，硬编码的 AI 可以用来创建一个聪明的对手，你可以挑战经典的井字游戏！但是，该算法仍然可以进一步优化。但我们如何做到这一点？Alpha B

短命女/ 2023年09月28日 09:49/ 0 赞/ 100 阅读

相关 UOJ#468. 【ZJOI2019】Minimax搜索动态DP

原文链接www.cnblogs.com/zhouzhendong/p/UOJ468.html 前言毒瘤题题解首先，将问题稍加转化，将“等于k”转化为“小于

绝地灬酷狼/ 2023年08月17日 16:21/ 0 赞/ 100 阅读

相关 Learnable Triangulation of Human Pose 论文解读

paper title: Learnable Triangulation of Human Pose paper link:https://arxiv.org/abs/19

﹏ヽ暗。殇╰゛Y/ 2022年12月24日 00:35/ 0 赞/ 142 阅读

相关 LightOJ 1331-Agent J【计算几何】

1331 - Agent J <table> <tbody> <tr> <td title="special judge" style="color:rgb

Love The Way You Lie/ 2022年08月21日 12:51/ 0 赞/ 109 阅读

相关 uva 1331——Minimax Triangulation

题意：三角刨分，把一个m边形分解成m-2个三角形，求一个最大三角形最小的刨分，输出最小的那个三角形面积。思路：递推。可能需要一点几何思维，d（i，j）为多边形的最

╰+哭是因爲堅強的太久メ/ 2022年08月18日 02:42/ 0 赞/ 124 阅读

相关【lightoj1331】Agent J【计算几何】

F - F 圆周率用acos(-1.0) 使用longlong Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:

你的名字/ 2022年07月17日 01:43/ 0 赞/ 49 阅读

相关 Minimax算法及实例分析

计算机科学中最有趣的事情之一就是编写一个人机博弈的程序。有大量的例子，最出名的是编写一个国际象棋的博弈机器。但不管是什么游戏，程序趋向于遵循一个被称为Minimax算法，伴随着

ゞ浴缸里的玫瑰/ 2022年05月29日 09:35/ 0 赞/ 268 阅读

相关「PKUWC2018」Minimax

[ 传送门 ][Link 1] Solution > 发现叶子节点的值都不样，所以可以线段树合并。 > > 然后因为我们要维护一个后缀，所以我们先合并右儿子，在

左手的ㄟ右手/ 2021年12月22日 00:13/ 0 赞/ 180 阅读

相关 UVa 1331 最大面积最小的三角剖分

题意：输入一个多边形（不一定是凸包），找一个最大三角形面积最小的三角剖分，输出最大三角形的面积。分析：最优三角剖分。dp\[i\]\[j\]表示从i点到j点的最优值,

左手的ㄟ右手/ 2021年12月18日 14:41/ 0 赞/ 224 阅读

相关 D - Minimax Problem （二分、状压）

[题目][Link 1] 思路：首先暴力想一想这道题，把每两组数都模拟一遍取最大值，O(N^2)。然后看有没有什么地方可以改进，会发现这题可以适用于二分，看可以用二分的条

深藏阁楼爱情的钟/ 2021年07月16日 14:38/ 0 赞/ 313 阅读