A3016 · 公交车 · GESP考级

题目描述

某城市有个能容纳 $n$ 辆公交车的停车场。每一天，这些公交车都要依次有序离开停车库去另一个终点站。这终点站距离停车场有 $d$ 米的路程。当然第 $i$ 辆公交车离开停车场的时间是 $t_i$ 秒，并以最大速度不超过 $v_i$ 米/秒行驶，加速度最大值为 $a$。一辆公交车能瞬间减速，也能瞬间改变它的加速度。当然每辆车的最大加速度都一样为 $a$。 不管有多大的马力，一辆公交车都不能超过其他另外的公交车，如果一辆公交车追上另一辆公交车，那么后面追上的车跟前面被追的车一起并排行驶同时到达终点站。当然司机都是尽可能快的驾车到达终点站的。 作为公交公司老板的你，希望每辆公交车都尽可能快的到达终点站。当然，公交车到达终点站时，速度可以没必要达到 $0$。当一辆公交车离开停车场时，它的起始速度等于 $0$。通过物理的观点解释的话，公交车可以看成是抽象的一个物体而已，除了能加速和减速，其他对速度的影响都可以忽略掉。

第一行三个空格隔开的整数 $n, a, d$（$1 \leq n \leq 10^5$，$1 \leq a, d \leq 10^6$），分别表示公交车的数量，最大加速度。离终点站的距离。 接下来 $n$ 行，每行有一对整数 $t_i, v_i$（$0 \leq t_1 < t_2 < \cdots < t_{n-1} < tn \leq 10^6$，$1 \leq v_i \leq 10^6$），分别表示每辆车离开停车场的时刻和能够行驶的最大速度。

输出每辆公交车到达终点站的时刻。一行表示一辆公交车的到达时刻，输出时刻的公交车顺序按照输入的公交车顺序。输出答案的相对或绝对误差不能超过 $10^{-4}$（即末尾保留 $4$ 位小数）。

输入 #1

输出 #1

1000.5000
1000.5000
11000.0500