#P2433. [Noi2011]智能车比赛

[Noi2011]智能车比赛

题目描述

赛道由 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,2x_{i,1}<x_{i,2}、yi,1<yi,2y_{i,1}<y_{i,2}。相邻矩形满足 xi,2=xi+1,1x_{i,2}=x_{i+1,1},并且它们的纵坐标区间有交集,车辆可以通过重叠的边。

车辆从赛道上的 SS 出发,驶到赛道上的 TT。车辆不能离开赛道,行驶速度恒为 vv,转向不消耗时间。求最短时间。

输入格式

第一行一个整数 nn(1≤n≤20001\le n\le2000)。接下来 nn 行,每行依次给出 xi,1,yi,1,xi,2,yi,2x_{i,1},y_{i,1},x_{i,2},y_{i,2}。随后两行分别给出起点 xS,ySx_S,y_S 和终点 xT,yTx_T,y_T。所有坐标均为绝对值不超过 4000040000 的整数。最后一行给出实数 vv(1≤v≤101\le v\le10)。

输出格式

输出一个实数,表示最快到达时间。绝对误差不超过 10−610^{-6} 即可。

样例

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

CCF NOI 2011 第一试原卷