题目描述
赛道由 n 个边平行于坐标轴的闭矩形拼成。第 i 个矩形的左下角为 (xi,1,yi,1),右上角为 (xi,2,yi,2)。每个矩形满足 xi,1<xi,2、yi,1<yi,2。相邻矩形满足 xi,2=xi+1,1,并且它们的纵坐标区间有交集,车辆可以通过重叠的边。
车辆从赛道上的 S 出发,驶到赛道上的 T。车辆不能离开赛道,行驶速度恒为 v,转向不消耗时间。求最短时间。
输入格式
第一行一个整数 n(1≤n≤2000)。接下来 n 行,每行依次给出 xi,1,yi,1,xi,2,yi,2。随后两行分别给出起点 xS,yS 和终点 xT,yT。所有坐标均为绝对值不超过 40000 的整数。最后一行给出实数 v(1≤v≤10)。
输出格式
输出一个实数,表示最快到达时间。绝对误差不超过 10−6 即可。
样例
2
1 1 2 2
2 0 3 4
1 1
3 0
1.0
2.41421356
CCF NOI 2011 第一试原卷