题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2433
题意:若干个矩形排成一排（同一个x之上最多有一个矩形），矩形i和i+1相邻。给定两点S和T，两点均在矩形内。求S到T的最短路径。只能在矩形内部走。
思路：首先，S到T若有转弯，必定是在矩形的顶点处转弯。因此，只要建立任意两可达顶点（包含S和T）之间距离求最短路即可。若暴力枚举任意两点再判是否可达复杂度O(n^3)。优化。枚举起点a，从左向右扫遍矩形，利用叉积维护关于该点a的上下界，在该范围之内的点均可达。
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <map>
#define abs(x) ((x)>=0?(x):-(x))
#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long
#define clr(x,y) memset(x,y,sizeof(x))
#define CLR(x) x.clear()
#define ph(x) push(x)
#define pb(x) push_back(x)
#define Len(x) x.length()
#define SZ(x) x.size()
#define PI acos(-1.0)
#define sqr(x) ((x)*(x))
#define MP(x,y) make_pair(x,y)
#define EPS 1e-10
#define FOR0(i,x) for(i=0;i<x;i++)
#define FOR1(i,x) for(i=1;i<=x;i++)
#define FOR(i,a,b) for(i=a;i<=b;i++)
#define FORL0(i,a) for(i=a;i>=0;i--)
#define FORL1(i,a) for(i=a;i>=1;i--)
#define FORL(i,a,b)for(i=a;i>=b;i--)
#define rush() int CC;for(scanf("%d",&CC);CC--;)
#define Rush(n) while(scanf("%d",&n)!=-1)
using namespace std;
void RD(int &x){scanf("%d",&x);}
void RD(i64 &x){scanf("%lld",&x);}
void RD(u64 &x){scanf("%I64u",&x);}
void RD(u32 &x){scanf("%u",&x);}
void RD(double &x){scanf("%lf",&x);}
void RD(int &x,int &y){scanf("%d%d",&x,&y);}
void RD(i64 &x,i64 &y){scanf("%lld%lld",&x,&y);}
void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}
void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}
void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void RD(i64 &x,i64 &y,i64 &z){scanf("%lld%lld%lld",&x,&y,&z);}
void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}
void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}
void RD(char &x){x=getchar();}
void RD(char *s){scanf("%s",s);}
void RD(string &s){cin>>s;}
void PR(int x) {printf("%d\n",x);}
void PR(int x,int y) {printf("%d %d\n",x,y);}
void PR(i64 x) {printf("%lld\n",x);}
void PR(u32 x) {printf("%u\n",x);}
void PR(u64 x) {printf("%llu\n",x);}
void PR(double x) {printf("%.10lf\n",x);}
void PR(char x) {printf("%c\n",x);}
void PR(char *x) {printf("%s\n",x);}
void PR(string x) {cout<<x<<endl;}
const int mod=10007;
const i64 inf=((i64)1)<<60;
const double dinf=1e100;
const int INF=1000000005;
const int N=50005;
struct point
{
int x,y;
point(){}
point(int _x,int _y)
{
x=_x;
y=_y;
}
void get()
{
RD(x,y);
}
point operator-(point a)
{
return point(x-a.x,y-a.y);
}
i64 operator*(point a)
{
return (i64)x*a.y-(i64)y*a.x;
}
double len()
{
return sqrt(1.0*x*x+1.0*y*y);
}
};
struct node
{
point a,b,c,d;
void get()
{
int x1,y1,x2,y2;
RD(x1,y1); RD(x2,y2);
a=point(x1,y1);
b=point(x1,y2);
c=point(x2,y1);
d=point(x2,y2);
}
int contain(point p)
{
return a.x<=p.x&&p.x<=c.x&&a.y<=p.y&&p.y<=b.y;
}
};
double f[N],v,ans;
node a[N];
point S,T;
int n;
double dis(point a,point b)
{
a=a-b;
return a.len();
}
i64 cross(point a,point b,point c)
{
return (b-a)*(c-a);
}
int isCross(point a,point b,point c,point d)
{
if(b.x<a.x) return 0;
return cross(a,c,b)<=0&&cross(a,d,b)>=0;
}
void update(point S,int now,double p)
{
if(p>=dinf) return;
point up=point(S.x,S.y+1);
point down=point(S.x,S.y-1);
point l,r;
int i;
for(i=now;i<n;i++)
{
if(isCross(S,a[i].a,up,down)) f[i*4]=min(f[i*4],p+dis(S,a[i].a));
if(isCross(S,a[i].b,up,down)) f[i*4+1]=min(f[i*4+1],p+dis(S,a[i].b));
if(isCross(S,a[i].c,up,down)) f[i*4+2]=min(f[i*4+2],p+dis(S,a[i].c));
if(isCross(S,a[i].d,up,down)) f[i*4+3]=min(f[i*4+3],p+dis(S,a[i].d));
if(a[i].contain(T)&&isCross(S,T,up,down)) ans=min(ans,p+dis(S,T));
if(i+1<n)
{
l=point(a[i].c.x,max(a[i].c.y,a[i+1].a.y));
r=point(a[i].d.x,min(a[i].d.y,a[i+1].b.y));
if(a[i].c.x==S.x)
{
if(l.y>S.y||S.y>r.y)
{
f[(i+1)*4]=min(f[(i+1)*4],p+dis(S,a[i+1].a));
f[(i+1)*4+1]=min(f[(i+1)*4+1],p+dis(S,a[i+1].b));
return;
}
}
else
{
if(cross(S,down,l)>0) down=l;
if(cross(S,up,r)<0) up=r;
if(cross(S,up,down)>0) return;
}
}
}
}
int main()
{
RD(n);
int i;
FOR0(i,n) a[i].get();
S.get(); T.get();
RD(v);
if(S.x>T.x) swap(S,T);
FOR0(i,4*n) f[i]=dinf;
ans=dinf;
FOR0(i,n)
{
if(a[i].contain(S)) update(S,i,0);
update(a[i].a,i,f[i*4]);
update(a[i].b,i,f[i*4+1]);
update(a[i].c,i,f[i*4+2]);
update(a[i].d,i,f[i*4+3]);
}
PR(ans/v);
}