#P17868. 白夜 3

白夜 3

L. 白夜 3

给定严格凸多边形的 nn 个顶点,按逆时针顺序排列,坐标为 (xi,yi)(x_i,y_i)。

将每个顶点染成青色或白色。分别对两种颜色的点求凸包 Hc,HwH_c,H_w。求交集 Hc∩HwH_c\cap H_w 的最大可能面积。

允许某种颜色没有点。空集的凸包为空;点或线段的面积为零。

输入格式

第一行 TT,1≤T≤1041\le T\le10^4。每组先给出 nn,随后 nn 行,每行两个整数 xi,yix_i,y_i。

3≤n≤1053\le n\le10^5,−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9。保证点两两不同,按逆时针组成严格凸多边形。所有测试的 nn 之和不超过 10510^5。

输出格式

每组输出一个实数。设你的答案为 aa,标准答案为 bb,要求 ∣a−b∣≤10−8max⁡(1,∣b∣)|a-b|\le10^{-8}\max(1,|b|)。

样例 1

输入:

3
7
0 0
3 0
4 1
3 3
1 4
-1 3
-1 1
5
0 0
2 0
3 1
1 3
-1 1
7
-1000000000 -1000000000
-500000001 -500000002
499999998 499999995
999999998 999999994
500000000 499999997
-499999999 -500000000
-999999999 -999999999

输出:

5.944444444444444444
0
2.458333333333333404