QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100

#5612. 蓄势待发

统计

气象学家 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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.