New Year and Curling (Codeforces 908C)
Tags: Implement, geometry

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 = 10100.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 (xi, 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. Compute the y-coordinates of centers of all the disks after all disks have been pushed.

Input: 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.The next line will contain n integers x1, x2, ..., xn (1 ≤ xi ≤ 1 000) — the x-coordinates of the disks.

Output: 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.

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

Sample Inputs:
6 2
5 5 6 8 3 12

Sample Outputs:
2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613

Solution (Python):
from math import sqrt

def main():
    (n, r) = map(float, input().split())
    d = r * 2.0
    d2 = d * d
    l = []
    for x in map(float, input().split()):
        (le, ri, h) = (x - d, x + d, r)
        for (u, v) in l:
            if le <= u <= ri:
                w = x - u
                y = v + sqrt(d2 - w * w)
                if h < y:
                    h = y
        l.append((x, h))
        print(h, end=' ')
if __name__ == '__main__':
    main()

Solution (Python):
(n, r) = map(int, input().split())
lst = list(map(int, input().split()))
result = []
for i in lst:
    val = r
    for (x, j) in result:
        if abs(x - i) <= 2 * r:
            val = max(val, (4 * r * r - (x - i) ** 2) ** 0.5 + j)
    result.append([i, val])
    print(val, end=' ')

Solution (Python):
def y_coord(n, r, x):
    y = [0] * n
    for i in range(n):
        y[i] = r
        for j in range(i):
            if abs(x[i] - x[j]) <= 2 * r:
                y_coord = y[j] + (4 * r ** 2 - (x[i] - x[j]) ** 2) ** 0.5
                y[i] = max(y[i], y_coord)
    return y
i = input()
(n, r) = map(int, i.split())
x = list(map(int, input().split()))
y = y_coord(n, r, x)
print(' '.join(map(str, y)))