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;
}