#P1995. [NOI2011] 智能车比赛

    ID: 1018 远端评测题 1000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp计算几何2011NOI 系列Special Judge最短路

[NOI2011] 智能车比赛

题目描述

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

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

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

输入格式

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

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

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

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

接下来一行包含一个实数 vv,表示智能车的速度。

输出格式

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

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

2  
1 1 2 2  
2 0 3 4  
1 1  
3 0  
1.0 
2.41421356

提示