UVA1331 最大面积最小的三角剖分 Minimax Triangulation
题目描述
给定一个 $n$ 条边的多边形（不一定是凸多边形），用 $n-3$ 条线段（线段必须连接多边形上的两点，每条线段都必须在多边形的内部，并且任意两条线段都不能在多边形内相交）把多边形剖分成 $n-2$ 个三角形，试找出一个切割方案，使得最大的三角形面积最小。
输入格式
**本题单个测试点内包含多组测试数据。**
第一行，一个整数 $T$，表示有 $T$ 组测试数据；
对于每组测试数据：
- 第一行，一个整数 $n$，表示多边形顶点数量；
- 接下来 $n$ 行，$n$ 个整数 $x_i,y_i$，描述多边形的 $n$ 个顶点。
输出格式
对于每组测试数据，输出一行一个实数，表示最大面积的最小值。**保留 $\boldsymbol{1}$ 位小数。**
### 样例
- 输入
```
1
6
7 0
6 2
9 5
3 5
0 3
1 1
```
- 输出
```
9.0
```
说明/提示
对于 $100\%$ 的数据，保证：
- $3\le n\le 49$；
- $0\le x_i,y_i\le 10\,000$；
- 顶点是以顺时针或逆时针顺序给出的。
由 xyz32768 和 Starrykiller 提供翻译。