304759: CF908C. New Year and Curling

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF908C/259203790d90e969d73ec841bd0673c1e8e7d69a.png) 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: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF908C/d83c8ae09a1afba1002e3c764e58c1e7ac4abfee.png)In particular, note the position of the last disk.

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: