← 返回题目列表

Codeforces · 908/C

C. 新年和冰壶

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

卡罗尔目前正在进行冰壶运动。

她在 2D 平面上有 n 个圆盘,每个圆盘的半径为 r。

最初,她拥有 y = 10100 线上方的所有这些磁盘。

然后,她将按照从 1 到 n 的顺序将圆盘向 y = 0 线滑动。

当她滑动第 i 个圆盘时,她会将其中心放置在点 (xi, 10100) 上。然后她将推动它,使圆盘的 y 坐标不断减小,而 x 坐标保持不变。一旦接触到线 y = 0 或接触到任何先前的圆盘,圆盘就会停止。请注意,一旦磁盘停止移动,即使被另一个磁盘击中,它也不会再次移动。

计算所有磁盘被推送后的所有磁盘中心的 y 坐标。

输入

第一行将包含两个整数 n 和 r (1 ≤ n, r ≤ 1 000),分别是圆盘的数量和圆盘的半径。

下一行将包含 n 个整数 x1, x2, ..., xn (1 ≤ xi ≤ 1 000) - 磁盘的 x 坐标。

输出

打印一行包含 n 个数字的内容。第 i 个数字表示第 i 个圆盘中心的 y 坐标。如果输出的绝对或相对误差最多为 10 - 6,则输出将被接受。

也就是说,假设您对特定坐标值的答案是 a,陪审团的答案是 b。如果所有坐标的 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$ ,检查程序将认为您的答案正确。

示例

输入 #1

6 2
5 5 6 8 3 12

输出 #1

2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613

注意

磁盘的最终位置如下所示:

特别要注意最后一个磁盘的位置。