Problem: Example

Input

100 1 0
50 100


Output

14.57738

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << endl

typedef double D;

struct Node {
  D p;
  D h;
};

const D EPS = 1e-10;

int sig(D a, D b) {
  if(a < b - EPS) return -1;
  if(a > b + EPS) return +1;
  return 0;
}

bool check(D th, D speed, D start, D end, const vector<Node> &objs) {
  D vx = speed * cos(th);
  D vy = speed * sin(th);
  bool ok = true;
  for(int i = 0; i < (int)objs.size(); ++i) {
    if(sig(start, objs[i].p) <= 0 && sig(objs[i].p, end) <= 0) {
      D x = objs[i].p - start;
      D y = -(x*x/(2*vx*vx)) + vy*x/vx;
      if(sig(y, objs[i].h) < 0) {
        ok = false;
      }
    }
  }
  return ok;
}

D speed(D th, D len) {
  return sqrt(len / (sin(2*th)));
}

void test(D th, D len, D pos) {
  D sp = speed(th, len);
  D vx = sp * cos(th);
  D vy = sp * sin(th);
  D y = -(pos*pos/(2*vx*vx)) + (vy/vx)*pos;
  DEBUG(y);
}

int main() {
  D distance;
  int N, B;
  cin >> distance >> N >> B;
  vector<Node> objs(N);
  for(int i = 0; i < N; ++i) {
    cin >> objs[i].p >> objs[i].h;
  }
  B++;
  D ans = 1e20;
  for(int b = 1; b <= B; ++b) {
    for(int i = 0; i < b; ++i) {
      D start = distance / b * i;
      D end = distance / b * (i + 1);
      D len = abs(end - start);
      D estm;
      // DEBUG(start);
      // DEBUG(end);
      // DEBUG(len);
      // DEBUG(speed(M_PI/4, len));
      // D vx = speed(M_PI/4, len)*cos(M_PI/4);
      // D vy = speed(M_PI/4, len)*sin(M_PI/4);
      // DEBUG(-(len*len/(2*vx*vx))+(vy/vx)*len);
        // DEBUG("false");
      D lb = M_PI/4, ub = M_PI/2;
      for(int t = 0; t < 300; ++t) {
        D mid = (lb + ub) / 2;
        if(check(mid, speed(mid, len), start, end, objs)) {
          ub = mid;
        }
        else {
          lb = mid;
        }
      }
      estm = ub;
      D estm_sp = speed(estm, len);
      bool ok = true;
      for(int j = 0; j < b; ++j) {
        D start2 = distance / b * j;
        D end2 = distance / b * (j + 1);
        if(check(estm, estm_sp, start2, end2, objs) == false) {
          ok = false;
        }
      }
      if(ok) {
        ans = min(ans, estm_sp);
      }
    }
  }
  cout.setf(ios::fixed); cout.precision(10);
  cout << ans << endl;
}