问题描述

我们需要计算在一个包含障碍墙的密闭空间内，从起点$(0,5)$到终点$(10,5)$的最短路径长度。该密闭空间的边界固定为$x=0$、$x=10$、$y=0$和$y=10$。空间内部可能包含$0$到$18$道垂直墙壁，每道墙上有两个门洞。

示例说明

图示密闭空间对应的输入数据为：

2
4 2 7 8 9
7 3 4.5 6 7

其中最短路径长度计算结果为$10.06$（如原题图示）

输入格式

• 多组测试数据，以$-1$结束
• 每组数据：
  • 第一行：墙壁数量$n$（$0 \leq n \leq 18$）
  • 接下来$n$行：每行描述一道墙，包含$5$个实数：
    • 第一个数：墙壁的$x$坐标（$0 < x < 10$）
    • 后四个数：门洞的$y$坐标端点（按升序排列）
• 墙壁$x$坐标按升序排列

输出格式

• 对每组数据输出一行，表示最短路径长度（保留两位小数）

输入输出示例

输入

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

输出

10.00
10.06

计算原理

1. 空间建模：将密闭空间视为二维平面，边界为$x \in [0,10]$，$y \in [0,10]$
2. 障碍处理：每道垂直墙$W_i$在$x=x_i$处，门洞范围为$[y_{i1},y_{i2}]$和$[y_{i3},y_{i4}]$
3. 路径规划：通过门洞的连通性计算最短路径，需满足：
   • 路径由直线段组成
   • 每段直线必须穿过有效门洞
   • 路径总长度$L = \sum \sqrt{(x_{k+1}-x_k)^2 + (y_{k+1}-y_k)^2}$

实现要求

程序需要处理多组测试数据，对每组数据：

1. 解析墙壁和门洞信息
2. 构建可达性图（将门洞端点作为节点）
3. 应用图搜索算法（如Dijkstra算法）计算最短路径
4. 输出结果保留两位小数

注意：当$n=0$时，最短路径即为直线距离$\sqrt{(10-0)^2 + (5-5)^2} = 10.00$