题目大意

给定一个村庄的轮廓折线 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，$x$ 坐标递增。
要在 $[x_1, x_n]$ 范围内建一座瞭望塔，塔顶必须能看到轮廓上任意位置。
求塔的最小高度（塔高 = 塔顶高度 - 塔基高度，塔基高度由轮廓在该位置的 $y$ 值决定）。

问题分析

1. 可见性的几何条件

从塔顶 $T = (X, H_{\text{top}})$ 能看到轮廓上任意点 $P$，意味着线段 $TP$ 除了 $P$ 点外，不与轮廓相交，并且整个轮廓在 $TP$ 的下方。
这等价于：塔顶 $T$ 必须在轮廓的每条边所在直线的上方。

2. 转化为半平面交

对于轮廓的每条边 $(x_i, y_i) \to (x_{i+1}, y_{i+1})$，可以写出直线方程。
将这条边看作有向线段（从左到右），那么塔顶 $T$ 必须位于该线段的左侧（即上方）。
这样，每条边对应一个半平面约束。

3. 可行区域

所有 $n-1$ 条边对应的半平面交集是一个凸多边形区域（可能无界），表示所有可能的塔顶位置 $(X, Y)$。
由于 $X \in [x_1, x_n]$，我们只考虑该凸多边形在区间 $[x_1, x_n]$ 内的部分。

4. 最小化塔高

在位置 $X$ 处，轮廓高度为 $f(X)$（由轮廓折线线性插值得到）。
塔高 = $Y - f(X)$，其中 $(X, Y)$ 是可行区域中的点。
目标是在可行区域中寻找 $\min (Y - f(X))$。

5. 候选点

最小值可能出现的位置：

• 半平面交多边形的顶点（在 $[x_1, x_n]$ 区间内）；
• 轮廓折线的顶点正上方（即 $X = x_i$ 时，$Y$ 取可行区域的最小可能值）。

因此，只需枚举：

• 所有半平面交的顶点；
• 所有轮廓顶点 $x_i$ 对应的可行区域最小 $Y$（由半平面交在该 $x_i$ 处的下边界确定）。

算法步骤

1. 对轮廓的 $n-1$ 条边，构造半平面（左侧为可行区域）。
2. 用半平面交算法（如 S&I 算法）求可行凸多边形。
3. 收集所有半平面交顶点，以及轮廓顶点 $x_i$ 对应的半平面交下边界 $Y$ 值。
4. 计算每个候选点的塔高 $Y - f(X)$，取最小值。
5. 输出最小值，保留三位小数。

复杂度

• 半平面交 $O(n \log n)$。
• $n \le 300$，足够高效。

关键点

• 将“能看到整个轮廓”转化为“塔顶在每条轮廓边的上方半平面”。
• 半平面交得到可行区域。
• 最小值出现在半平面交的顶点或轮廓顶点上方。