Problem: Example

Input

100 1 0
50 100


Output

14.57738

Solution (in CPP):

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

constexpr int MAX_N = 10;

int dist, n, max_bound;
double p[MAX_N], h[MAX_N];

constexpr double EPS = 1e-8;

vector<double> solve_quadratic_equation(double a, double b, double c) {
	if(abs(a) <= EPS) {
		if(abs(b) <= EPS) {
			if(abs(c) <= EPS) return {0};
			return {};
		}
		return {-c / b};
	}

	const double d = b * b - 4 * a * c;
	if(d < 0) return {};

	return {(-b - sqrt(d)) / (2 * a), (-b + sqrt(d)) / (2 * a)};
}

double calc_y(double vx, double vy, double x) {
	return - (1.0 / (2.0 * vx * vx)) * (x * x) + (vy / vx) * x;
}

double calc_vx(double x, double y, double theta) {
	const double a = (x * sin(theta) / cos(theta) - y);
	const double b = 0.0;
	const double c = - x * x / 2.0;

	double res = 0.0;
	for(const auto &e : solve_quadratic_equation(a, b, c)) {
		if(e > 0.0) {
			res = e;
			break;
		}
	}

	return res;
}

double calc_vy(double vx, double theta) {
	return vx * sin(theta) / cos(theta);
}

bool check(int bound, double theta) {
	const double jump_dist = dist / (bound + 1.0);
	const double vx = calc_vx(jump_dist, 0, theta);
	const double vy = calc_vy(vx, theta);

	for(int i = 0; i < n; ++i) {
		double s = 0.0;
		while(s + jump_dist + EPS < p[i]) {
			s += jump_dist;
		}

		if(calc_y(vx, vy, p[i] - s) + EPS < h[i]) return false;
	}
	
	return true;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(10);

	cin >> dist >> n >> max_bound;

	for(int i = 0; i < n; ++i) {
		cin >> p[i] >> h[i];
	}

	double ans = INT_MAX;
	for(int bound = 0; bound <= max_bound; ++bound) {
		double L = M_PI / 4.0, R = M_PI / 2.0;

		for(int i = 0; i < 100; ++i) {
			const double M = (L + R) / 2;

			if(check(bound, M)) {
				R = M;
			}
			else {
				L = M;
			}
		}

		const double vx = calc_vx(dist / (bound + 1.0), 0, L);
		const double vy = calc_vy(vx, L);
		ans = min(ans, vx * vx + vy * vy);
	}

	cout << sqrt(ans) << endl;

	return EXIT_SUCCESS;
}