1 #include<iostream>  2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6  7 const int maxn = 50 + 5; 8 const int INF = 100000000; 9 10 int n;11 int x[maxn], y[maxn];12 double d[maxn][maxn];13 14 //行列式求三角形面积15 double area(int a, int b, int c)16 {17     double s = (double)(1.0 / 2)*(x[a] * y[b] + x[b] * y[c] + x[c] * y[a] - x[a] * y[c] - x[b] * y[a] - x[c] * y[b]);18     if (s<0) return -s;19     return s;20 }21 22 //判断三角形内部是否有点23 bool check(int a, int b, int c)24 {25     int i;26     for (i = 1; i <= n; i++)27     {28         if (i == a || i == b || i == c) continue;29         double d = area(a, b, i) + area(a, c, i) + area(b, c, i) - area(a, b, c);30         if (d<0) d = -d;31         if (d <= 0.01) return 0;32     }33     return 1;34 }35 36 37 int main()38 {39     //freopen("D:\\txt.txt", "r", stdin);40     int T;41     cin >> T;42     while (T--)43     {44         cin >> n;45         for (int i = 1; i <= n; i++)46             cin >> x[i] >> y[i];47         for (int i = n; i >= 1; i--)48         {49             d[i][i+1] = 0;50             for (int j = i + 2; j <= n; j++)51             {52                 d[i][j] = INF;53                 for (int k = i + 1; k < j; k++)54                 {55                     if (check(i, j, k))56                         d[i][j] = min(d[i][j], max(max(area(i, j, k), d[i][k]), d[k][j]));57                 }58             }59         }60         printf("%.1lf\n", d[1][n]);61     }62     return 0;63 }