#P17868. 白夜 3
白夜 3
L. 白夜 3
给定严格凸多边形的 个顶点,按逆时针顺序排列,坐标为 。
将每个顶点染成青色或白色。分别对两种颜色的点求凸包 。求交集 的最大可能面积。
允许某种颜色没有点。空集的凸包为空;点或线段的面积为零。
输入格式
第一行 ,。每组先给出 ,随后 行,每行两个整数 。
,。保证点两两不同,按逆时针组成严格凸多边形。所有测试的 之和不超过 。
输出格式
每组输出一个实数。设你的答案为 ,标准答案为 ,要求 。
样例 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