气象学家 Wendy Wynne Blose 和地质学家 Maddy Morfik 正在中亚的多孔山脉(Porous Mountains)研究地下喷出的过热烟雾和蒸汽。与 1980 年圣海伦斯火山爆发那种剧烈喷发不同,这些较温和的事件涉及蒸汽通过(极度多孔的)地面上的许多微小裂缝喷出,在保持地表完整的同时,产生了一团可见的云,并向上升起。Wendy 和 Maddy 希望通过视频捕捉这种云的路径。
像所有优秀的科学家一样,他们做出了一些简化假设。他们假设云是球形的,具有已知的半径,并以固定的已知速度沿直线运动。他们还假设云将在地下形成并沿特定方向喷出,始终能够穿过疏松的山岩,且速度、方向或形状不会发生变化。科学家们拥有非常精密的仪器,能够很好地预测这种地下蒸汽云何时喷出。最后,他们建立了一个周围山脉的模型,形式为连续的分段线性近似。
出于安全考虑,他们将架设一台摄像机和一个计时器,在预测到蒸汽云首次从摄像机的视点可见的瞬间开启摄像机;然后他们将前往远处的一个安全地点,等待录制完成。图 1 展示了一个典型场景。位于 $(2, 2)$ 的摄像机需要对准 $(5, 5)$ 处的山峰,以便在云首次在 $(6, 6)$ 处可见时捕捉到它。如果云的半径为 $1$ 个单位,并以每秒 $1$ 个单位的速度从其地下起始点 $(13, -1)$ 沿向量 $[-1, 1]$(即 $135$ 度角)的方向移动,则摄像机应在 $8.899$ 秒后开启。
图 1:第一个样例输入
为了从摄像机电池中获得最大的录制时间,他们需要知道开启摄像机的精确时间。这就是你需要做的事情。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 1\,000$),表示定义山脉的线段数量,随后是 $n + 1$ 个整数对 $(x_i, y_i)$ ($-5\,000 \le x_0 < \dots < x_n \le 5\,000, 0 \le y_i \le 5\,000$),其中 $(x_{i-1}, y_{i-1})$ 和 $(x_i, y_i)$ 定义了第 $i$ 条线段的端点。任意三个连续点不会共线。第二行包含七个整数 $c, sx, sy, r, dx, dy, v$,其中 $c$ ($x_0 \le c \le x_n$) 指定了摄像机沿山脉位置的 $x$ 坐标,$(sx, sy)$ ($x_0 \le sx \le x_n, -5\,000 \le sy \le 5\,000$) 指定了蒸汽云的初始地下位置,$r$ ($1 \le r \le 5\,000$) 是云的半径,$dx$ 和 $dy$ ($-5\,000 \le dx \le 5\,000, 1 \le dy \le 5\,000$) 指定了蒸汽移动方向的向量形式(每 $dx$ 个单位的水平距离对应 $dy$ 个单位的垂直距离),$v$ ($1 \le v \le 1\,000$) 是云的速度(单位:单位/秒)。
输出格式
输出一个实数 $t$,即应开启摄像机的时间(秒),也就是在 $x_0$ 和 $x_n$ 之间的位置首次能看到非零体积的可见云的时间。假设云从时间 $0$ 开始从其起始点移动,并从该点开始保持恒定的速度和方向。云将首先从地下出现在 $x$ 坐标位于 $x_0$ 和 $x_n$ 之间的某一点。如果摄像机永远不可能在 $x$ 坐标位于 $x_0$ 和 $x_n$ 之间的点观察到云,则输出 $-1$。答案应具有 $10^{-3}$ 的绝对或相对误差精度。
样例
样例输入 1
7 1 0 2 2 4 2 5 5 6 0 9 4 12 3 14 0 2 13 -1 1 -1 1 1
样例输出 1
8.899