#2443. 「NOI2011」智能车比赛

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: luyanaa

题目描述

新一届智能车大赛在 JL 大学开始啦!比赛赛道可以看作是由 nnn 个矩形区域拼接而成(如下图所示),每个矩形的边都平行于坐标轴,第 iii 个矩形区域的左下角和右上角坐标分别为 (xi,1,yi,1)(x_{i,1} ,y_{i,1})(xi,1,yi,1)(xi,2,yi,2)(x_{i,2} ,y_{i,2} )(xi,2,yi,2)

题目保证:xi,1<xi,2=xi+1,1x_{i,1} <x_{i,2} =x_{i+1,1}xi,1<xi,2=xi+1,1,且 yi,1<yi,2y_{i,1} < y_{i,2}yi,1<yi,2,相邻两个矩形一定有重叠在一起的边(如图中虚线所示),智能车可以通过这部分穿梭于矩形区域之间。

选手们需要在最快的时间内让自己设计的智能车从一个给定的起点 SSS 点到达一个给定的终点 TTT 点,且智能车不能跑出赛道。假定智能车的速度恒为 vvv 且转向不消耗任何时间,你能算出最快需要多少时间完成比赛么?

输入格式

输入的第一行包含一个正整数 nnn,表示组成赛道的矩形个数。

接下来 nnn 行描述这些矩形,其中第 iii 行包含 444 个整数 xi,1,yi,1,xi,2,yi,2x_{i,1}, y_{i,1} , x_{i,2} , y_{i,2}xi,1,yi,1,xi,2,yi,2,表示第 iii 个矩形左下角和右上角坐标分别为 (xi,1,yi,1)(x_{i,1} , y_{i,1} )(xi,1,yi,1)(xi,2,yi,2)(x_{i,2} , y_{i,2} )(xi,2,yi,2)

接下来一行包含两个整数 xSx_SxSySy_SyS,表示起点坐标。

接下来一行包含两个整数 xTx_TxTyTy_TyT,表示终点坐标。

接下来一行包含一个实数 vvv1≤v≤101 \le v \le 101v10),表示智能车的速度。

输出格式

仅输出一个实数,至少精确到小数点后第六位,为智能车完成比赛的最快时间。

对于每个测试点,如果你的输出结果和参考结果相差不超过 106,该测试点得满分,否则不得分。

样例

样例输入

2
1 12 2
203 4
1 1
30
1.0

样例输出

2.41421356

数据范围与提示

对于 10%10\%10% 的数据,有 n≤1n \le 1n1.

对于 30%30\%30% 的数据,有 n≤5n \le 5n5.

对于 60%60\%60% 的数据,有 n≤200n \le 200n200.

对于 100%100\%100% 的数据,有 n≤2000n \le 2000n2000.

保证所有坐标均为整数且绝对值不超过 400004000040000.