C. New Year and Curling

Carol 目前正在玩冰壶。 她在二维平面上有 #cf_span[n] 个半径为 #cf_span[r] 的圆盘。 最初，所有这些圆盘都位于直线 #cf_span[y = 10100] 上方。 然后她将按从 #cf_span[1] 到 #cf_span[n] 的顺序，逐个将圆盘向直线 #cf_span[y = 0] 推动。 当她推动第 #cf_span[i] 个圆盘时，她会将其圆心放置在点 #cf_span[(xi, 10100)] 处，然后推动它，使得圆盘的 #cf_span[y] 坐标持续减小，而 #cf_span[x] 坐标保持不变。圆盘一旦触及直线 #cf_span[y = 0] 或任何先前放置的圆盘，就会停止移动。注意，一旦圆盘停止移动，即使被其他圆盘撞击，也不会再移动。 请计算所有圆盘被推动后，每个圆盘圆心的 #cf_span[y]-坐标。 第一行包含两个整数 #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]-坐标。 请输出一行包含 #cf_span[n] 个数字。第 #cf_span[i] 个数字表示第 #cf_span[i] 个圆盘圆心的 #cf_span[y]-坐标。输出的绝对误差或相对误差不超过 #cf_span[10 - 6] 即可被接受。 具体而言，假设你对某个坐标计算的答案为 #cf_span[a]，标准答案为 #cf_span[b]，评测程序将认为你的答案正确，当且仅当对所有坐标满足 。 所有圆盘最终的位置如下所示： 特别注意最后一个圆盘的位置。 ## Input 第一行包含两个整数 #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]-坐标。 ## Output 请输出一行包含 #cf_span[n] 个数字。第 #cf_span[i] 个数字表示第 #cf_span[i] 个圆盘圆心的 #cf_span[y]-坐标。输出的绝对误差或相对误差不超过 #cf_span[10 - 6] 即可被接受。具体而言，假设你对某个坐标计算的答案为 #cf_span[a]，标准答案为 #cf_span[b]，评测程序将认为你的答案正确，当且仅当对所有坐标满足 。 [samples] ## Note 所有圆盘最终的位置如下所示： 特别注意最后一个圆盘的位置。

**Definitions** Let $ n, r \in \mathbb{Z}^+ $ be the number of disks and the radius of each disk, respectively. Let $ \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. Let $ y_i \in \mathbb{R} $ denote the final $ y $-coordinate of the center of the $ i $-th disk. **Constraints** 1. $ 1 \leq n, r \leq 1000 $ 2. $ 1 \leq x_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $ 3. Each disk is initially placed at $ (x_i, 10100) $ and moves vertically downward until it touches $ y = 0 $ or a previous disk. 4. Disks are processed in order $ i = 1 $ to $ n $. 5. 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 $. **Objective** For each $ i \in \{1, \dots, n\} $, compute $ y_i $ such that: - $ 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 $. - For $ i > 1 $: $$ y_i = \max\left(r,\ \max_{j=1}^{i-1} \left\{ \sqrt{(x_i - x_j)^2 - (2r)^2 + y_j^2} \right\} \right) $$ if $ |x_i - x_j| \leq 2r $, otherwise the disk falls freely to $ y_i = r $. More precisely: $$ y_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) $$ Wait — correction: If disk $ i $ is above disk $ j $, and horizontal distance is $ d = |x_i - x_j| $, then vertical separation must satisfy: $$ (y_i - y_j)^2 + d^2 = (2r)^2 \Rightarrow y_i = y_j + \sqrt{(2r)^2 - d^2} $$ So: $$ y_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) $$ **Final Objective** For each $ i \in \{1, \dots, n\} $, compute: $$ y_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) $$