Codeforces Good Bye 2017: C. New Year and Curling

,

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

Hackチャンスだったのに気付くのが遅すぎた (終了3分前)。

problem

カーリングをする。 半径$r$の石を$n$個順に、$x$座標は$x_i$で$y$軸と平行に、$y = 10^{100}$から$y = 0$へ向かって投げる。 他の石あるいは$x$軸に触れた瞬間に停止する。 全て投げ終わった後の状態を答えよ。

solution

書くだけ。$O(n^2)$。

注意としては、衝突するのは必ずしも後に投げた石とは限らないこと。例えば次のケース。

4 1
4 4 1 2

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int n, r; scanf("%d%d", &n, &r);
    vector<int> x(n); REP (i, n) scanf("%d", &x[i]);
    // solve
    vector<double> y(n, r);
    REP (i, n) {
        REP (j, i) {
            int dx = abs(x[j] - x[i]);
            if (dx > 2 * r) continue;
            double dy = sqrt(pow(2 * r, 2) - pow(dx, 2));
            chmax(y[i], y[j] + dy);
        }
    }
    // output
    REP (i, n) {
        printf("%.10lf%c", y[i], i < n - 1 ? ' ' : '\n');
    }
    return 0;
}