最大面积最小的三角剖分 Minimax Triangulation

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define mistake(P) ( fabs ( P ) < eps ? 0 : (P < 0 ? -1 : 1) ) // 精度误差判断正负
#define db double
#define vec point
const db eps = 1e-10;
struct point {
	db x , y ;
	point ( db X = 0 , db Y = 0 ) : x ( X ) , y ( Y ) {}
};
vec operator + ( vec x , vec y ) { return vec ( x . x + y . x , x . y + y . y ) ; }
vec operator - ( vec x , vec y ) { return vec ( x . x - y . x , x . y - y . y ) ; }
vec operator * ( vec x , db y ) { return vec ( x . x * y , x . y * y ) ; }
bool operator == ( vec x , vec y ) { return mistake ( x . x - y . x ) == 0 and mistake ( x . y - y . y ) == 0 ; }
db dot_product ( vec x , vec y ) { return x . x * y . x + x . y * y . y ; }
db cross_product ( vec x , vec y ) { return x . x * y . y - x . y * y . x ; }
db length ( vec x ) { return sqrt ( dot_product ( x , x ) ) ; }
double areas ( vec x , vec y , vec z ) { return cross_product ( y - x , z - x ) ; }
//判断 x 是否在 a , b 中间。
bool zzj ( point x , point a , point b ) {
	return 
		mistake ( cross_product ( a - x , b - x ) ) == 0 
	and 
		mistake ( dot_product ( a - x , b - x ) ) < 0 ; 
}
//运用叉积计算 x2 , y2 在 向量 x1 -> y1 and x2 -> y2 的两侧 来判断向量是否相交。
bool pdxj ( point x1 , point y1 , point x2 , point y2 ) {
	db a = cross_product ( y1 - x1 , x2 - x1 ) , b = cross_product ( y1 - x1 , y2 - x1 ) ;
	db c = cross_product ( y2 - x2 , x1 - x2 ) , d = cross_product ( y2 - x2 , y1 - x2 ) ; 
	return mistake ( a ) * mistake ( b ) < 0 and mistake ( c ) * mistake ( d ) < 0 ;
}
bool pdzdbxn ( vector<vec> & vecs , vec cx ) {
	int num = vecs . size() , flag = 0 ;
	for ( int i = 0 ; i < num ; i ++ ){
		vec x = vecs [ i ] , y = vecs [ ( i + 1 ) % num ] ;
		if ( x == cx || y == cx || zzj ( cx , x , y ) ) return false;
		int k = mistake ( cross_product ( y - x , cx - x ) ) ;
		int a = mistake ( x . y - cx . y ) ;
		int b = mistake ( y . y - cx . y ) ;
		if ( k > 0 and a <= 0 and b > 0 ) flag ++ ;
		if ( k < 0 and b <= 0 and a > 0 ) flag -- ;
	}
	if ( flag != 0 ) return true;
	return false;
}
bool zdbxn ( vector<vec> & vecs , int x , int y ) {
	int num = vecs . size();
	for ( int i = 0 ; i < num ; i ++ ) {
		if ( i == x and i == y ) continue;
		if ( zzj ( vecs [ i ] , vecs [ x ] , vecs [ y ] ) ) return false ;
	}
	for ( int i = 0 ; i < num ; i ++ ) {
		if ( pdxj ( vecs [ i ] , vecs [ ( i + 1 ) % num ] , vecs [ x ] , vecs [ y ] ) ) return false ;
	}
	vec adds = vecs [ x ] + vecs [ y ] ;
	adds = adds * 0.5 ; 
	return pdzdbxn ( vecs , adds ) ; 
}
db f [ 100 ] [ 100 ] ;
void dp ( vector<vec> & vecs ) {
	int n = vecs . size();
	for ( int i = 0 ; i < n ; i ++ ) 
		for ( int j = 0 ; j < n ; j ++ ) 
			f [ i ] [ j ] = -1 ;
	for ( int len = 2 ; len <= n ; len ++ ) {
		for ( int i = 0 ; i + len - 1 < n ; i ++ ) {
			int j = i + len - 1 ;
			if ( j == i + 1 ) { f [ i ] [ j ] = 0 ; continue ; }
			if ( ! ( i == 0 and j == n - 1 ) and ! zdbxn ( vecs , i , j ) ) { f [ i ] [ j ] = 100000000.00 ; continue; }
			f [ i ] [ j ] = 100000000.00 ;
			for ( int k = i + 1 ; k < j ; k ++ ) {
				db work = fabs ( cross_product ( vecs [ j ] - vecs [ i ]  ,  vecs [ k ] - vecs [ i ] ) ) / 2.000;
				f [ i ] [ j ] = min ( f [ i ] [ j ] , max ( f [ i ] [ k ] , max ( f [ k ] [ j ] , work ) ) ) ;
			}
		}
	}
	printf ( "%.1lf\n" , f [ 0 ] [ n - 1 ] ) ;
}
int work () {
	vector<vec> vecs;
	int n ; cin >> n ;
	for ( int i = 0 ; i < n ; i ++ ) {
		static db x , y ; 
		scanf ( "%lf%lf" , & x , & y ) ;
		vecs . push_back ( vec ( x , y ) ) ;
	}
	dp(vecs);
	return 0 ;
}
int main(){
    int T ; cin >> T ;
    while ( T -- ) work();
}