#LUOGUP826. 公交车

公交车

题目描述

某城市有个能容纳 nn 辆公交车的停车场。每一天,这些公交车都要依次有序离开停车库去另一个终点站。这终点站距离停车场有 dd 米的路程。当然第 ii 辆公交车离开停车场的时间是 tit_i 秒,并以最大速度不超过 viv_i 米/秒行驶,加速度最大值为 aa。一辆公交车能瞬间减速,也能瞬间改变它的加速度。当然每辆车的最大加速度都一样为 aa

不管有多大的马力,一辆公交车都不能超过其他另外的公交车,如果一辆公交车追上另一辆公交车,那么后面追上的车跟前面被追的车一起并排行驶同时到达终点站。当然司机都是尽可能快的驾车到达终点站的。

作为公交公司老板的你,希望每辆公交车都尽可能快的到达终点站。当然,公交车到达终点站时,速度可以没必要达到 00。当一辆公交车离开停车场时,它的起始速度等于 00。通过物理的观点解释的话,公交车可以看成是抽象的一个物体而已,除了能加速和减速,其他对速度的影响都可以忽略掉。

输入格式

第一行三个空格隔开的整数 n,a,dn, a, d1n1051 \leq n \leq 10^51a,d1061 \leq a, d \leq 10^6),分别表示公交车的数量,最大加速度。离终点站的距离。

接下来 nn 行,每行有一对整数 ti,vit_i, v_i0t1<t2<<tn1<tn1060 \leq t_1 < t_2 < \cdots < t_{n-1} < tn \leq 10^61vi1061 \leq v_i \leq 10^6),分别表示每辆车离开停车场的时刻和能够行驶的最大速度。

输出格式

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

3 10 10000
0 10
5 11
1000 1

1000.5000
1000.5000
11000.0500

提示

【样例解释】

第二辆公交车能追上第一辆公交车,在行驶到距离终点 510.5510.5 公里处。然后还剩 9489.59489.5 公里的路程,两辆车都以 1010 km/h 的速度,一起到达终点的,它们到达终点的时刻是 1000.51000.5 秒,第三辆公交车不能赶上其他的公交车,他到达终点的时刻是 11000.0511000.05 秒。