908C.md (2036B)
1 Source: https://codeforces.com/problemset/problem/908/C 2 3 C. New Year and Curling 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Carol is currently curling. 22 23 She has *n* disks each with radius *r* on the 2D plane. 24 25 Initially she has all these disks above the line *y* = 10100. 26 27 She then will slide the disks towards the line *y* = 0 one by one in order from 1 to *n*. 28 29 When 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. 30 31 Compute the *y*-coordinates of centers of all the disks after all disks have been pushed. 32 33 Input 34 35 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. 36 37 The next line will contain *n* integers *x*1, *x*2, ..., *x**n* (1 ≤ *x**i* ≤ 1 000) — the *x*-coordinates of the disks. 38 39 Output 40 41 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. 42 43 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. 44 45 Example 46 47 Input 48 49 ``` 50 6 2 51 5 5 6 8 3 12 52 ``` 53 54 Output 55 56 ``` 57 2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613 58 ``` 59 60 Note 61 62 The final positions of the disks will look as follows: 63 64  65 66 In particular, note the position of the last disk.