#P1354. 房间最短路问题

    ID: 398 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学计算几何福建省历届夏令营

房间最短路问题

题目描述

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

输入格式

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

接下来 nn 排,每排 55 个实数 x,a1,b1,a2,b2x,a_1,b_1,a_2,b_2

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

a1,b1,a2,b2a_1,b_1,a_2,b_2 保持递增,x1xnx_1 \sim x_n 也是递增的。

输出格式

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

2
4 2 7 8 9
7 3 4.5 6 7

10.06