1052 - 计算几何:最短线路

通过次数

3

提交次数

4

时间限制 : 1 秒
内存限制 : 256 MB

在一个长宽均为 10,入口、出口分别为 (0,5)(10,5) 的房间里,有几堵墙,每堵墙上有两个缺口,求入口到出口的最短路经。

输入

第一排为 nn \le 20),墙的数目。

接下来 n 排,每排 5 个实数 x,a_1,b_1,a_2,b_2

x 表示墙的横坐标(所有墙都是竖直的),a_1 \sim b_1a_2 \sim b_2 之间为空缺。

a_1,b_1,a_2,b_2 保持递增,x_1 \sim x_n 也是递增的。

输出

输出最短距离,保留 2 位小数。

样例

输入

2
4 2 7 8 9
7 3 4.5 6 7

输出

10.06