P15784 [JAG 2025 Summer Camp #3] Fireworks

有 $N$ 栋公寓楼沿一条直线等间距排列。第 $i$ 栋楼（$1 \leq i \leq N$）位于坐标 $i \times L$ 处，高度为 $H_i$。 今年将举办一场烟花节，每栋楼的居民都希望从自家楼顶观看烟花。然而，根据烟花发射位置的不同，他们的视线可能会被其他楼房阻挡。为了避免这种情况，对于每个给定的发射坐标 $X_j$，需要确定一个最小高度，使得所有居民都能看到烟花。 更形式化地说，对于每个 $X_j$，找出一个最小的**非负**实数 $h_j$，使得不存在下标 $a, b$（$1 \leq a, b \leq N$）满足以下条件：连接点 $(a \times L, H_a)$ 与点 $(X_j, h_j)$ 的线段（不含端点）与连接点 $(b \times L, 0)$ 和点 $(b \times L, H_b)$ 的线段（不含端点）相交。

输入包含一个单独的测试用例，格式如下。 $$\begin{aligned} & N \ L \ Q \\ & H_{1} \ H_{2} \ \ldots \ H_{N} \\ & X_{1} \\ & \vdots \\ & X_{Q} \end{aligned}$$ 第一行包含三个整数 $N$（$1 \leq N \leq 300\,000$）、$L$（$1 \leq L \leq 1\,000$）和 $Q$（$1 \leq Q \leq 300\,000$），分别表示公寓楼的数量、相邻楼房的间距以及候选发射坐标的数量。 第二行包含 $N$ 个整数 $H_i$（$1 \leq H_i \leq 10^9$），表示第 $i$ 栋楼的高度。 接下来的 $Q$ 行，每行包含一个整数 $X_j$（$-10^9 \leq X_j \leq 10^9$，且 $X_j \neq i \times L$，其中 $i = 1, \ldots, N$），表示一个烟花发射的候选坐标。

对于 $Q$ 个询问，将答案逐行输出。在第 $j$ 行，输出当烟花在坐标 $X_j$ 发射时所需的最小发射高度。当答案的绝对误差或相对误差小于 $10^{-6}$ 时，即被视为正确。

翻译由 DeepSeek V3.2 完成