Description

 新一届智能车大赛在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且转向不消耗任何时间，你能算出最快需要多少时间完成比赛么？

Input

 输入的第一行包含一个正整数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，表示智能车的速度。

Output

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

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

Sample Input

2

1 12 2

203 4

1 1

30

1.0

Sample Output

2.41421356

HINT

有精度误差，请不要提交

N<=2000,所输入数字为绝对值小于40000的整数

 

囧，其实是一道比较简单的dp，一直犯了一个sb错误，没有好好地更新视野，我只用了视野中的点更新视野，操蛋

我们可以从左到右dp，判断是否可以到达，然后更新ans，这个我们只要记录两个点，一个是视野的上界，一个是视野的下界，然后没有视野就break，非常快

1 const  2     maxn=2020;  3     inf=99999999999999;  4 type  5     point=record  6         x,y:longint;  7     end;  8    9 function max(x,y:longint):longint; 10 begin 11     if x>y then exit(x); 12     exit(y); 13 end; 14   15 function min(x,y:longint):longint; 16 begin 17     if x
      
       y then exit(x); 30     exit(y); 31 end; 32   33 procedure swap(var x,y:point); 34 var 35     t:point; 36 begin 37     t:=x;x:=y;y:=t; 38 end; 39   40 operator -(a,b:point)c:point; 41 begin 42     c.x:=a.x-b.x; 43     c.y:=a.y-b.y; 44 end; 45   46 operator *(a,b:point)c:longint; 47 begin 48     exit(a.x*b.y-a.y*b.x); 49 end; 50   51 function dis(a,b:point):double; 52 begin 53     exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))); 54 end; 55   56 var 57     a:array[0..maxn,0..1]of point; 58     f:array[0..maxn,0..1]of double; 59     s,t:point; 60     n:longint; 61     v:double; 62   63 procedure main; 64 var 65     i,j,k,l,r:longint; 66     up,down:point; 67 begin 68     read(n); 69     for i:=1 to n do 70         read(a[i,0].x,a[i,0].y,a[i,1].x,a[i,1].y); 71     read(s.x,s.y,t.x,t.y,v); 72     if s.x>t.x then swap(s,t); 73     l:=n;r:=1; 74     while (a[l,0].x>s.x) or (a[l,0].y>s.y) or (a[l,1].x
       
        t.x) or (a[r,0].y>t.y) or (a[r,1].x
        
         =0) and ((down-a[i,j])*(a[k,1]-a[i,j])>=0) then 95                         f[k,1]:=min(f[k,1],f[i,j]+dis(a[i,j],a[k,1])/v); 96                         if  ((a[k,0]-a[i,j])*(up-a[i,j])>=0) and ((down-a[i,j])*(a[k,0]-a[i,j])>=0) then 97                         f[k,0]:=min(f[k,0],f[i,j]+dis(a[i,j],a[k,0])/v); 98                         if (a[k,1]-a[i,j])*(up-a[i,j])>=0 then up:=a[k,1]; 99                         if (down-a[i,j])*(a[k,0]-a[i,j])>=0 then down:=a[k,0];100                     end;101             end;102     writeln(f[r,0]:0:10);103 end;104  105 begin106     main;107 end.