← 返回题目列表

AtCoder · tricky_5

E. 云与影

中文机器翻译题面 查看原题

問題文

xy 平面为地面,距地面垂直方向为 z 取轴。
在这个问题中,我们将太阳视为一个点(点光源),将云视为没有厚度的多边形。
这个世界上没有太阳 2 有一个,坐标 它位于 ({8192}^{65536},\ {8192}^{65536},\ {8192}^{65536}) 和 按字典顺序比较 (-{8192}^{65536},\ -{8192}^{65536},\ {8192}^{65536}) 。 对于满足
天上有云 H,即 它在 z = H 平面上,并且可能不止一个。
云阻挡了阳光,并在太阳光线无法到达的地面上投射阴影。
地面上现在有一个多边形的阴影。 1 完成了。
给定地面阴影的形状,找到云总面积的最小值。

入力

第一行是测试用例的数量 T 。
之后的行包括 T 测试用例如下。

对于每个测试用例 1 阴影多边形的顶点数显示在行中 N 和云的位置。 z 坐标值 在一行中输出 H 由半角空格分隔。 关于
之后 N 行显示每个顶点。 x 坐标和 y 坐标以半角空格分隔。
这里,多边形的顶点是顺时针或逆时针给出的。

制約

  • T,\ N 如下 2 满足两个条件之一。
    • 0 \leq T \leq 4096 和 3 \leq N \leq 16
    • T = 1 和 N = 2048
  • 1 \leq H \leq 64 在 H 是一个整数
  • 多边形的各顶点坐标的绝对值为 32 不超过
  • 多边形的各顶点坐标为小数点以下恰好 2 位的小数给出
  • 多边形是简单的。也就是说不自相交
  • 多边形连续的 3 个顶点不在同一条直线上

出力

对于每个测试用例,请输出云的总面积最小值。
此时,小数第 3 位四舍五入,保留到小数第 2 位。

入力例

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

作者:laycrs 一组