AOJ 1348 Space Golf
解法
完全にやるだけ.多少無駄なことをしても入力サイズが小さいので余裕で通る.
ご丁寧に式が書かれているので,それに従って候補を全部列挙し,それらが条件をみたすか(つまり接触しないか)を判定する.条件をみたす中で最小の値が答え.
明らかに最適なのは vx = vy となるときで,これでうまくいかないならどれかに接触してしまうということ.その時は,接触するギリギリを全て試してみて,その中で条件を満たし,かつ最小の値を求める.
g = 9.8 じゃないので注意.
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr double INF = 1e9; constexpr double eps = 1e-8; int main() { double d; int n, b; cin >> d >> n >> b; vector<double> p(n), h(n); for(int i=0; i<n; ++i) { cin >> p[i] >> h[i]; } double res = INF; for(int i=0; i<=b; ++i) { double interval = d / (i+1); bool neg = false; for(int j=0; j<=i; ++j) { for(int i=0; i<n; ++i) { neg |= abs(interval * j - p[i]) < eps; } } if(neg) { continue; } vector<double> vx, vy; vx.push_back(sqrt(interval / 2)); vy.push_back(vx.back()); for(int j=0; j<=i; ++j) { double now = interval * j; for(int k=0; k<n; ++k) { double pp = p[k] - now; if(0 < pp && pp < interval) { vx.push_back(sqrt(1 / (2*h[k]) * pp * (interval - pp))); vy.push_back(interval / (2 * vx.back())); } } } for(int j=0; j<vx.size(); ++j) { bool ok = true; for(int k=0; k<=i; ++k) { double now = interval * k; for(int l=0; l<n; ++l) { double pp = p[l] - now; if(0 < pp && pp < interval) { double t = pp / vx[j]; double hh = vy[j] * t - 0.5 * t*t; ok &= (hh - h[l]) >= -eps; } } } if(ok) { res = min(res, hypot(vx[j], vy[j])); } } } cout << fixed << setprecision(10) << res << endl; }