{"raw_statement":[{"iden":"statement","content":"Carol is currently curling.\n\nShe has _n_ disks each with radius _r_ on the 2D plane.\n\nInitially she has all these disks above the line _y_ = 10100.\n\nShe then will slide the disks towards the line _y_ = 0 one by one in order from 1 to _n_.\n\nWhen she slides the _i_\\-th disk, she will place its center at the point (_x__i_, 10100). 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.\n\nCompute the _y_\\-coordinates of centers of all the disks after all disks have been pushed."},{"iden":"input","content":"The first line will contain two integers _n_ and _r_ (1 ≤ _n_, _r_ ≤ 1 000), the number of disks, and the radius of the disks, respectively.\n\nThe next line will contain _n_ integers _x_1, _x_2, ..., _x__n_ (1 ≤ _x__i_ ≤ 1 000) — the _x_\\-coordinates of the disks."},{"iden":"output","content":"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.\n\nNamely, 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."},{"iden":"example","content":"Input\n\n6 2\n5 5 6 8 3 12\n\nOutput\n\n2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613"},{"iden":"note","content":"The final positions of the disks will look as follows:\n\n<center>![image](https://espresso.codeforces.com/948fcb53d93866a46a676ebf7919a7a6476bca60.png)</center>In particular, note the position of the last disk."}],"translated_statement":[{"iden":"statement","content":"Carol 目前正在玩冰壶。\n\n她在二维平面上有 #cf_span[n] 个半径为 #cf_span[r] 的圆盘。\n\n最初，所有这些圆盘都位于直线 #cf_span[y = 10100] 上方。\n\n然后她将按从 #cf_span[1] 到 #cf_span[n] 的顺序，逐个将圆盘向直线 #cf_span[y = 0] 推动。\n\n当她推动第 #cf_span[i] 个圆盘时，她会将其圆心放置在点 #cf_span[(xi, 10100)] 处，然后推动它，使得圆盘的 #cf_span[y] 坐标持续减小，而 #cf_span[x] 坐标保持不变。圆盘一旦触及直线 #cf_span[y = 0] 或任何先前放置的圆盘，就会停止移动。注意，一旦圆盘停止移动，即使被其他圆盘撞击，也不会再移动。\n\n请计算所有圆盘被推动后，每个圆盘圆心的 #cf_span[y]-坐标。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[r] (#cf_span[1 ≤ n, r ≤ 1 000])，分别表示圆盘的数量和半径。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[1 ≤ xi ≤ 1 000]) —— 表示每个圆盘的 #cf_span[x]-坐标。\n\n请输出一行包含 #cf_span[n] 个数字。第 #cf_span[i] 个数字表示第 #cf_span[i] 个圆盘圆心的 #cf_span[y]-坐标。输出的绝对误差或相对误差不超过 #cf_span[10 - 6] 即可被接受。\n\n具体而言，假设你对某个坐标计算的答案为 #cf_span[a]，标准答案为 #cf_span[b]，评测程序将认为你的答案正确，当且仅当对所有坐标满足  。\n\n所有圆盘最终的位置如下所示：\n\n特别注意最后一个圆盘的位置。 \n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[r] (#cf_span[1 ≤ n, r ≤ 1 000])，分别表示圆盘的数量和半径。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[1 ≤ xi ≤ 1 000]) —— 表示每个圆盘的 #cf_span[x]-坐标。"},{"iden":"output","content":"请输出一行包含 #cf_span[n] 个数字。第 #cf_span[i] 个数字表示第 #cf_span[i] 个圆盘圆心的 #cf_span[y]-坐标。输出的绝对误差或相对误差不超过 #cf_span[10 - 6] 即可被接受。具体而言，假设你对某个坐标计算的答案为 #cf_span[a]，标准答案为 #cf_span[b]，评测程序将认为你的答案正确，当且仅当对所有坐标满足  。"},{"iden":"note","content":"所有圆盘最终的位置如下所示：  特别注意最后一个圆盘的位置。 "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, r \\in \\mathbb{Z}^+ $ be the number of disks and the radius of each disk, respectively.  \nLet $ \\mathbf{x} = (x_1, x_2, \\dots, x_n) \\in \\mathbb{R}^n $ be the sequence of $ x $-coordinates of the centers of the disks.  \nLet $ y_i \\in \\mathbb{R} $ denote the final $ y $-coordinate of the center of the $ i $-th disk.\n\n**Constraints**  \n1. $ 1 \\leq n, r \\leq 1000 $  \n2. $ 1 \\leq x_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Each disk is initially placed at $ (x_i, 10100) $ and moves vertically downward until it touches $ y = 0 $ or a previous disk.  \n4. Disks are processed in order $ i = 1 $ to $ n $.  \n5. A disk stops when its bottom point reaches $ y = 0 $ (i.e., center at $ y = r $) or when it touches another disk — meaning the Euclidean distance between centers equals $ 2r $.\n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, compute $ y_i $ such that:  \n- $ y_1 = \\min(10100 - r, r) $ if no prior disk, but since it falls until touching $ y=0 $, $ y_1 = r $ if $ 10100 - r \\geq r $, which always holds → $ y_1 = r $.  \n- For $ i > 1 $:  \n  $$\n  y_i = \\max\\left(r,\\ \\max_{j=1}^{i-1} \\left\\{ \\sqrt{(x_i - x_j)^2 - (2r)^2 + y_j^2} \\right\\} \\right)\n  $$  \n  if $ |x_i - x_j| \\leq 2r $, otherwise the disk falls freely to $ y_i = r $.  \n\nMore precisely:  \n$$\ny_i = \\max\\left( r,\\ \\max_{\\substack{j=1 \\\\ |x_i - x_j| \\leq 2r}}^{i-1} \\left( \\sqrt{(2r)^2 - (x_i - x_j)^2} + y_j \\right) \\right)\n$$  \nWait — correction:  \nIf disk $ i $ is above disk $ j $, and horizontal distance is $ d = |x_i - x_j| $, then vertical separation must satisfy:  \n$$\n(y_i - y_j)^2 + d^2 = (2r)^2 \\Rightarrow y_i = y_j + \\sqrt{(2r)^2 - d^2}\n$$  \nSo:  \n$$\ny_i = \\max\\left( r,\\ \\max_{\\substack{j=1 \\\\ |x_i - x_j| \\leq 2r}}^{i-1} \\left( y_j + \\sqrt{(2r)^2 - (x_i - x_j)^2} \\right) \\right)\n$$\n\n**Final Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, compute:  \n$$\ny_i = \\max\\left( r,\\ \\max_{\\substack{1 \\leq j < i \\\\ |x_i - x_j| \\leq 2r}} \\left( y_j + \\sqrt{4r^2 - (x_i - x_j)^2} \\right) \\right)\n$$","simple_statement":null,"has_page_source":false}