A16613 · Buses · GESP考级

题目描述

有一条长度为 $\ell$ 米的笔直公路，位置 $p$ 表示距离起点 $p$ 米的点。公路上有 $n$ 辆公交车沿正方向行驶，每辆公交的速度均为 $x$ 米每分钟。第 $i$ 辆公交当前位于 $s_i$ 处，会一直驶向它的目的地 $t_i$，到达后即停止运行，所有乘客必须下车。 同时有 $m$ 个人希望到达公路终点（位置 $\ell$）。第 $i$ 个人当前位置为 $p_i$，每个人最多能以 $y$ 米每分钟的速度步行。如果某人和公交位于同一位置，他可以立刻上车；在公交上可以随时下车。上下公交所需时间忽略不计。公交永远以速度 $x$ 匀速前进，不等人。 请你计算每个人到达终点所需的最短时间。 ![](/uploads/acgo/image/b9e9e549840c46e0ac48056a673ccd09_dce64a9753f2.png) 图 1：样例输入 1 的示意图。

第一行包含五个整数 $n$、$m$、$\ell$、$x$ 和 $y$，分别表示公交车数量、人员数量、公路长度、公交的速度和人的步行速度。 接下来的 $n$ 行，每行两个整数 $s_i$ 和 $t_i$，表示第 $i$ 辆公交的起点和终点位置。 接下来的 $m$ 行，每行一个整数 $p_i$，表示第 $i$ 个人的当前位置。 - $1 \leq n \leq 2 \times 10^5$ - $1 \leq m \leq 2 \times 10^5$ - $1 \leq \ell \leq 10^9$ - $1 \leq y < x \leq 10^6$ - $0 \leq s_i < t_i \leq \ell$ - $0 \leq p_i \leq \ell$

输出 $m$ 行，第 $i$ 行为第 $i$ 个人到达公路终点所需的最短时间（单位：分钟）。 如果你的答案与标准答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。正式地，设你的答案为 $a$，标准答案为 $b$，则当 $\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}$ 时视作正确。

输入 #1

输出 #1

6.25
1.5
5