Submission #1777877

---

Source Code Expand

#include<iostream>
#include"math.h"

int n, start, goal;
int l[200000], r[200000];
float rec(int x, int y, float num) {
	float res = 1000000;

	//ゴールへ(単数)
	if (n - y <= 1)
		res = num + sqrt((goal - x)*(goal - x) + 1);
	//ゴールへ(複数)
	for (int i = 1; i <= n - y - 1; i++)
		if (l[y + i]>x + (float)(goal - x)*i / (n - y) || x + (float)(goal - x)*i / (n - y)>r[y + i])
			goto flaga;
	res = res<num + sqrt((goal - x)*(goal - x) + (n - y)*(n - y)) ? res : num + sqrt((goal - x)*(goal - x) + (n - y)*(n - y));
flaga:
	//一つ次
	if (y<n-1) {
		res =
			res<rec(l[y + 1], y + 1, num + sqrt((l[y + 1] - x)*(l[y + 1] - x) + 1)) ?
			res : rec(l[y + 1], y + 1, num + sqrt((l[y + 1] - x)*(l[y + 1] - x) + 1));
		res =
			res<rec(r[y + 1], y + 1, num + sqrt((r[y + 1] - x)*(r[y + 1] - x) + 1)) ?
			res : rec(r[y + 1], y + 1, num + sqrt((r[y + 1] - x)*(r[y + 1] - x) + 1));
	}
	
	//複数次
	for (int i = 2; i <= n - y; i++) {
		for (int j = 1; j <= i - 1; j++) {
			if (l[y + j]>x + (float)(l[y + i] - x)*j / i || x + (float)(l[y + i] - x)*j / i>r[y + j])
				goto flagb;
		}
		res = res<rec(l[y + i], y + i, num + sqrt((l[y + i] - x)*(l[y + i] - x) + i*i)) ?
			res : rec(l[y + i], y + i, num + sqrt((l[y + i] - x)*(l[y + i] - x) + i*i));
	flagb:;
	}
	for (int i = 2; i <= n - y; i++) {
		for (int j = 1; j <= i - 1; j++) {
			if (l[y + j]>x + (float)(r[y + i] - x)*j / i || x + (float)(r[y + i] - x)*j / i>r[y + j])
				goto flagc;
		}
		res = res<rec(r[y + i], y + i, num + sqrt((r[y + i] - x)*(r[y + i] - x) + i*i)) ?
			res : rec(r[y + i], y + i, num + sqrt((r[y + i] - x)*(r[y + i] - x) + i*i));
	flagc:;
	}

	return res;
}
int main() {
	std::cin >> n >> start >> goal;
	for (int i = 0; i<n + 1; i++)
		std::cin >> l[i] >> r[i];
	std::cout << rec(start, 0, 0) << std::endl;
	return 0;
}

Submission Info

Judge Result