Problem: Example

Input

100 1 0
50 100


Output

14.57738

Solution (in CPP):

Solution:
#include <iostream>
#include <cmath>
#include <stdio.h>
#define eps 1.0e-8

using namespace std;

double d;
int n, b;
int p[15], h[15];
double coe[3];

void Lagrange(double x1, double y1, double x2, double y2, double x3, double y3)
{
	double x[] = {x1, x2, x3}, y[] = {y1, y2, y3};
	
	double l[3][3];
	for(int i = 0; i < 3; i++){
		l[i][0] = 1;
		l[i][1] = 0;
		for(int j = 0; j < 3; j++) if(i != j) l[i][1] -= x[j];
		l[i][2] = 1;
		for(int j = 0; j < 3; j++) if(i != j) l[i][2] *= x[j];
		double bunbo = 1;
		for(int j = 0; j < 3; j++) if(i != j) bunbo *= (x[i] - x[j]);
		for(int j = 0; j < 3; j++) l[i][j] /= bunbo;
	}
	for(int i = 0; i < 3; i++){
		coe[i] = 0;
		for(int j = 0; j < 3; j++){
			coe[i] += y[j] * l[j][i];
		}
	}
}
	

int main(void)
{
	cin >> d >> n >> b;
	for(int i = 0; i < n; i++) cin >> p[i] >> h[i];
	
	double ans = 1.0e10;
	double l, r;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= b; j++){
			for(int k = 0; k <= j; k++){
				l = d / (j+1) * k;
				r = d / (j+1) * (k+1);
				if(p[i] <= l || p[i] >= r) continue;
				Lagrange(0, 0, r-l, 0, p[i]-l, h[i]);
				
				bool flag = true;
				for(int z = 0; z < n; z++){
					int no = p[z] / (r-l);
					double x = p[z] - no*(r-l);
					double y = coe[0]*x*x + coe[1]*x + coe[2];
					if(y < h[z] - eps){
						flag = false;
						break;
					}
				}
				if(flag){
					double th = atan(coe[1]);
					double v = sqrt( -0.5 / (coe[0]*cos(th)*cos(th)) );
					ans = min(ans, v);
				}
			}
		}
	}
	
	for(int j = 0; j <= b; j++){
		l = 0.0;
		r = d / (j+1);
		coe[0] = -1.0 / (r-l);
		coe[1] = 1.0;
		coe[2] = 0.0;
		
		bool flag = true;
		for(int z = 0; z < n; z++){
			int no = p[z] / (r-l);
			double x = p[z] - no*(r-l);
			double y = coe[0]*x*x + coe[1]*x + coe[2];
			if(y < h[z] - eps){
				flag = false;
				break;
			}
		}
		if(flag){
			double th = atan(coe[1]);
			double v = sqrt( -0.5 / (coe[0]*cos(th)*cos(th)) );
			ans = min(ans, v);
		}
	}
	
	printf("%.8f\n", ans);
	return 0;
}