题目描述

给定平面上一个由互异点构成的集合 $S$，我们定义 凸洞 为一类凸多边形：其全部顶点均来自所给的点，且内部不包含任何所给的点。除顶点外，其他给定点允许落在该多边形的边界上。我们希望找出一个如上所述的凸洞，使得该凸多边形具有最大的面积。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试数据的总组数。对于每组测试数据，第一行包含一个整数 $n$（$3 \le n \le 50$）。接下来 $n$ 行，每行包含两个整数 $x$ 与 $y$，描述一个点，满足 $-1000 \le x, y \le 1000$。

我们保证至少存在一个非退化的凸多边形。

输出格式

对于每组测试数据，输出一行，表示空凸多边形的最大面积，保留一位小数。

注：由 Pick 定理关于整点坐标多边形的推论可知，其面积要么以 $.0$ 结尾，要么以 $.5$ 结尾。

4
3
0 0
1 0
0 1
5
0 0
1 0
2 0
0 1
1 1
5
0 0
3 0
4 1
3 5
-1 3
6
3 1
1 0
2 0
3 0
4 0
5 0

0.5
1.5
17.0
2.0

提示

翻译由 DeepSeek V3.2 完成