AT_tricky_5.雲と影

$xy$ 平面为地面，$z$ 轴自地面垂直向上。在本题中，太阳视为点光源，云视为无厚度的多边形。

这个世界有两个太阳，分别位于坐标 $({8192}^{65536},\ {8192}^{65536},\ {8192}^{65536})$ 和 $(-{8192}^{65536},\ -{8192}^{65536},\ {8192}^{65536})$。

云位于上空 $H$，即 $z = H$ 的平面上，可以有多个云。

云会遮挡太阳的光线，若某处地面无法被任一太阳照射，则该处会形成阴影。

现在，地面上形成了一个多边形形状的阴影。

给定地面上阴影的多边形形状，请求出云的总面积的最小值。

第一行输入测试用例的数量 $T$。

接下来有 $T$ 个测试用例。

每个测试用例的第一行给出阴影多边形的顶点数 $N$ 和云所在的 $z$ 坐标 $H$，用空格分隔。

接下来的 $N$ 行，每行给出一个顶点的 $x$ 坐标和 $y$ 坐标，用空格分隔。

多边形的顶点按顺时针或逆时针顺序给出。

• $T,\ N$ 满足以下两种情况之一：
  • $0 \leq T \leq 4096$ 且 $3 \leq N \leq 16$
  • $T = 1$ 且 $N = 2048$
• $1 \leq H \leq 64$，$H$ 为整数。
• 多边形每个顶点的坐标绝对值不超过 $32$。
• 多边形每个顶点的坐标为小数点后恰好两位的小数。
• 多边形为简单多边形，即无自交。
• 多边形任意连续三个顶点不共线。

对于每个测试用例，输出云的总面积的最小值。结果四舍五入保留两位小数。

例如：

2
4 5
0.00 1.00
1.00 1.00
1.00 0.00
0.00 0.00
3 64
0.00 1.00
1.00 0.00
0.00 0.00

输出：

2.00
1.00

第一行输入一个整数 $T$，表示测试用例数量。

对于每个测试用例：

第一行输入两个整数 $N$ 和 $H$，分别表示阴影多边形的顶点数和云的高度。

接下来的 $N$ 行，每行输入两个实数 $x$ 和 $y$，表示多边形一个顶点的坐标。

对于每个测试用例，输出一个实数，表示云的总面积的最小值。结果四舍五入保留两位小数。

无。

由 ChatGPT 4.1 翻译