A22585.智能车比赛
NOI/NOI+/CTSC
NOI
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
新一届智能车大赛在 JL 大学开始啦!比赛赛道可以看作是由 n 个矩形区域拼接而成(如下图所示),每个矩形的边都平行于坐标轴,第 i 个矩形区域的左下角和右上角坐标分别为 (xi,1,yi,1) 和 (xi,2,yi,2)。
题目保证:xi,1<xi,2=xi+1,1,且 yi,1<yi,2,相邻两个矩形一定有重叠在一起的边(如图中虚线所示),智能车可以通过这部分穿梭于矩形区域之间。
选手们需要在最快的时间内让自己设计的智能车从一个给定的起点 S 点到达一个给定的终点 T 点,且智能车不能跑出赛道。假定智能车的速度恒为 v 且转向不消耗任何时间,你能算出最快需要多少时间完成比赛么?
输入格式
输入的第一行包含一个正整数 n,表示组成赛道的矩形个数。
接下来 n 行描述这些矩形,其中第 i 行包含 4 个整数 xi,1,yi,1,xi,2,yi,2,表示第 i 个矩形左下角和右上角坐标分别为 (xi,1,yi,1) 和 (xi,2,yi,2)。
接下来一行包含两个整数 xS,yS,表示起点坐标。
接下来一行包含两个整数 xT,yT,表示终点坐标。
接下来一行包含一个实数 v,表示智能车的速度。
输出格式
仅输出一个实数,至少精确到小数点后第六位,为智能车完成比赛的最快时间。
对于每个测试点,如果你的输出结果和参考结果相差不超过 10−6,该测试点得满分,否则不得分。
输入输出样例
输入#1
2 1 1 2 2 2 0 3 4 1 1 3 0 1.0
输出#1
2.41421356