UVA 1331 Minimax Triangulation DP， 三角剖分

　　题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4077

　　题目大意： 给出一个多边形， 输出三角剖分最大三角形最小化的最大三角形面积

　　解题思路： 最大值最小化啊......猛然想到了二分， 但是这个是DP专题啊......d(i, j)表示多边形i ~ j的最优解， DP转移方程就是dp(i, j) = min(dp(i, j), max(dp(i, k), dp(k, j), get_Area(i, j, k)))

　　　　下标是可以循环的， 我们先枚举长度， 再枚举左端点，然后再枚举中的点。有个trick, 如果是三个点组成的三角形有内点的话， 这三个点组成的三角形面积不算。 画图就知道了。

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
using namespace std;

struct Node {
    double x, y;
};
Node a[55];
double d[55][55]; // d[i][j] z
const int INF = 0x3fffffff;
int m;
const double eps = 1e-9;

double area( int i, int j, int k ) {
    return 0.5 * abs(a[i].x*(a[j].y-a[k].y)+a[j].x*(a[k].y-a[i].y)+a[k].x*(a[i].y-a[j].y));
}

int judge( int p, int q, int r ) { // p, q, r组成的三角形无内点
    double cur = area(p, q, r);
    for( int i = 0; i < m; i++ ) {
        if( i == p || i == q || i == r ) continue;
        double temp = area(p, q, i) + area(q, r, i) + area(p, r, i);
        if( fabs(temp-cur) < eps ) return 0;
    }
    return 1;
}

int main() {
    int T;
    scanf( "%d", &T );
    while( T-- ) {
        memset(a, 0, sizeof(a));
        scanf( "%d", &m );
        for( int i = 0; i < m; i++ ) {
            scanf( "%lf%lf", &a[i].x, &a[i].y );
        }
        for( int i = 0; i < m; i++ ) {
            for( int j = 0; j < m; j++ ) {
                if( i == 0 || i == 1 ) d[j][(j+i)%m] = 0.;
                else if( i == 2 ) d[j][(j+i)%m] = area(j, (j+1)%m, (j+2)%m);
                else d[j][(j+i)%m] = INF;
            }
        }
        for( int k = 3; k < m; k++ ) {
            for( int i = 0; i < m; i++ ) {
                int t = (i+k)%m; // 右端点
//                d[i][t] = INF;
                for( int j = (i+1)%m; j != t; j = (j+1)%m ) {
                    if( judge(j, t, i) ) {
                        d[i][t] = min(d[i][t], max({d[i][j], d[j][t], area(i, j, t)}));
                    }
                }
            }
        }
//        for( int i = 0; i < m; i++ ) {
//            for( int j = 0; j < m; j++ ) {
//                printf( "%.1lf ", d[i][j] );
//            }
//            cout << endl;
//        }
        printf( "%.1lf
", d[0][m-1] );
    }
    return 0;
}

　　思考： 状态又想错了， 以后要是有点的话， 要考虑区间， 或者前i个点这种情况， 自己的心思不够缜密， 有好多漏解的情况， 还有Trick也想不到， 有时候真的感觉自己白学了一年......但是还是得接着学啊！