Problem: Example

Input

100 1 0
50 100


Output

14.57738

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for(int i = (int)(s); i < (int)(e); ++i)
#define rep(i, n) REP(i, 0, n)

#define X real()
#define Y imag()

using D = double;
using P = complex<D>;

const D EPS = 1e-8;
const D PI = acos(-1);

D SQ(D x) {return x*x;}

int main() {
    cout << fixed << setprecision(20);
    int d, n, b;
    cin >> d >> n >> b;
    vector<D> p(n), h(n);
    rep(i, n) {
        cin >> p[i] >> h[i];
    }
    D ans = 1e9;
    rep(k, b+1) {
        D l = PI/4.0, r = PI/2.0; // r => OK, l => NG
        D L = (D)d/(k+1.0);

        auto check = [&](D m, int B) {
            D v = sqrt(L/(2*sin(m)*cos(m)));
            D vx = v*cos(m), vy = v*sin(m);
            int j = 0;
            rep(i, B+1) {
                auto getY = [&]() {
                    D x = p[j]-L*i;
                    return -(1.0/(2*SQ(vx)))*SQ(x)+(vy/vx)*(x);
                };
                while(j < n && p[j] < L*(i+1) + EPS) {
                    if(getY() < h[j] - EPS) return false;
                    j++;
                }
            }
            return true;
        };

        rep(_, 100) {
            D m = (l+r)/2.0;
            if(check(m, k)) r = m;
            else l = m; 
        }
        // printf("l:%.15lf\n", l);
        ans = min(ans, sqrt(L/(2*sin(l)*cos(l))));
    }
    cout << ans << endl;
    return 0;
}