← 返回题目列表

Codeforces · 167/A

A. 奇才和无轨电车

中文机器翻译题面 查看原题

在一些国家生活着巫师。他们喜欢乘坐无轨电车。

这个国家的一个城市有一个无轨电车站,有 n 辆无轨电车。每天,无轨电车一辆接一辆地离开车站,前往终点站。终点站距车辆段 d 米。我们知道,第 i 辆无轨电车在 ti 秒时刻出发,行驶速度不大于每秒 vi 米,加速加速度不大于每秒 1 米平方。无轨电车可以随心所欲地减速(神奇!)。它也可以按照您想要的速度改变其加速度。请注意,所有手推车的最大加速度都是相同的。

尽管有魔力,手推车仍然由电路供电,并且无法超越对方(当然,电线是罪魁祸首)。如果一辆无轨电车追上另一辆无轨电车,它们就会一前一后地一起行驶,直到到达终点站。此外,司机们也在开车,以尽快到达终点站。

作为无轨电车粉丝俱乐部的负责人,您需要确定每辆无轨电车到达终点站的最短时间。在到达目的地车站时,无轨电车不一定是零速度。当电车离开车站时,其速度被视为为零。从物理学的角度来看,无轨电车可以被视为质点,而且我们应该忽略除了发动机提供的加速和减速之外的一切对无轨电车速度的影响。

输入

第一输入行包含三个空格分隔的整数 n, a, d (1 ≤ n ≤ 105, 1 ≤ a, d ≤ 106) — 无轨电车的数量、它们的最大加速度以及相应的从车站到终点站的距离。

接下来的 n 行包含整数对 ti vi (0 ≤ t1 < t2... < tn - 1 < tn ≤ 106, 1 ≤ vi ≤ 106) — 第 i 辆无轨电车离开车站的时间及其相应的最大速度。行中的数字由空格分隔。

输出

对于每辆无轨电车,在到达终点站时打印一行。按照输入中给出的无轨电车顺序打印无轨电车的时间。如果绝对误差或相对误差不超过 10 - 4,则答案将被接受。

示例

输入 #1

3 10 10000
0 10
5 11
1000 1

输出 #1

1000.5000000000
1000.5000000000
11000.0500000000

输入 #2

1 2 26
28 29

输出 #2

33.0990195136

注意

在第一个样本中,第二辆无轨电车将追上第一辆无轨电车,这将发生在距离车站 510.5 米的地方。无轨电车将以每秒 10 米的速度一起行驶剩余的 9489.5 米。结果,两辆无轨电车将在 1000.5 秒时到达终点站。第三辆无轨电车将追不上他们。它将在时间11000.05秒时到达终点站。