Codeforces Good Bye 2017: C. New Year and Curling
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;
}