New Year and Curling [Good Bye 2017 C]

http://codeforces.com/contest/908/problem/C

半径Rの円がN個ある。
i番目の円は(X[i], INF)から落として、y軸の負の方向へ動かしていく。
他の円にぶつかったら（接するのも含む）そこで止める。
1番目の円から順番に落としていく時に、各円のy座標はどうなるか？

解法

http://codeforces.com/contest/908/submission/33773242

シミュレーション。
i番目の円を落下させるときは、j=[0,i)番目の円について考えていく。
abs(X[i] - X[j])≦R*2の場合にぶつかる可能性があるので、その場合について考えていく。
　
もし1個もぶつかる可能性のあるものがないなら、y座標はRになる。
　
abs(X[i] - X[j])=R*2ならば、接することでぶつかると判定されるので、接した円と同じy座標で止まる。
　
abs(X[i] - X[j])＜R*2ならば、円jの中心からdだけ上で止まるとすると、「d^2+abs(X[i] - X[j])^2=(2R)^2」が成立する。
なので、「d = sqrt((2R)^2 - abs(X[i] - X[j])^2)」でdを計算し、「円jの中心のy座標+d」のy座標で止まる。
　
あとは、可能性のあるもののの中で一番上のものが最初にぶつかるやつなので、最大値を最終的な止まる地点とする。

int N, R, X[1010];
double ans[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> R;
    rep(i, 0, N) cin >> X[i];
    
    rep(i, 0, N) {
        
        ans[i] = -1;
        rep(j, 0, i) {
            if (abs(X[i] - X[j]) == R * 2) ans[i] = max(ans[i], ans[j]);
            else if (abs(X[i] - X[j]) < R * 2) {
                double a = abs(X[i] - X[j]);
                double b = R * 2;
                double c = sqrt(b * b - a * a);

                ans[i] = max(ans[i], ans[j] + c);
            }
        }

        if (ans[i] < 0) ans[i] = R;
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%.12f", ans[i]);
    }
    printf("\n");
}