New Year and Curling

题意翻译

题意： 已知一些圆在($x_i$,$10^{100}$)处，然后依次落下，下落时只要碰到某个圆，就会停止，求这些圆的最后的y值，也即是水平高度 相切也会停止，求的是圆心的y值 Translated by @远航之曲 @yybyyb

题目描述

Carol is currently curling. She has $ n $ disks each with radius $ r $ on the 2D plane. Initially she has all these disks above the line $ y=10^{100} $ . She then will slide the disks towards the line $ y=0 $ one by one in order from $ 1 $ to $ n $ . When she slides the $ i $ -th disk, she will place its center at the point $ (x_{i},10^{100}) $ . She will then push it so the disk’s $ y $ coordinate continuously decreases, and $ x $ coordinate stays constant. The disk stops once it touches the line $ y=0 $ or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk. Compute the $ y $ -coordinates of centers of all the disks after all disks have been pushed.

输入输出格式

输入格式

The first line will contain two integers $ n $ and $ r $ ( $ 1<=n,r<=1000 $ ), the number of disks, and the radius of the disks, respectively. The next line will contain $ n $ integers $ x_{1},x_{2},...,x_{n} $ ( $ 1<=x_{i}<=1000 $ ) — the $ x $ -coordinates of the disks.

输出格式

Print a single line with $ n $ numbers. The $ i $ -th number denotes the $ y $ -coordinate of the center of the $ i $ -th disk. The output will be accepted if it has absolute or relative error at most $ 10^{-6} $ . Namely, let's assume that your answer for a particular value of a coordinate is $ a $ and the answer of the jury is $ b $ . The checker program will consider your answer correct if  for all coordinates.

输入输出样例

输入样例 #1

6 2
5 5 6 8 3 12

输出样例 #1

2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613

说明

The final positions of the disks will look as follows: In particular, note the position of the last disk.