SPFA。
我们关键是要找到关键点，包括起点，终点，和相邻矩形接触线段的上端点和下端点（如图有红色圈住的点为关键点）。
我们要做的就是在这些关键点之间连边。
我们把这些关键的点拿出来:
其实就是一些竖直的线段。
除了S和T外，从左到右或者从右到左穿过线段所在的直线，必须在线段中穿过去，也就是说有个上边界和下边界。
如图是S到第4条竖直的线段的上边界l1和下边界l2。
我们先按X坐标从小到大排序，枚举边的起点，向左或者向右连边，如果遇到竖直的线段，用叉积更改上下边界即可。
构好图就直接SPFA即可。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int maxN=2000; const double INF=1e15; const double EPS=1e-9; inline int dblcmp(double x){if (abs(x)<EPS)return 0;return x>0?1:-1;} inline double sqr(double x){return x*x;} struct Tpoint { double x,y; inline Tpoint(){} inline Tpoint(double _x,double _y){x=_x;y=_y;} }; inline double dis(Tpoint a,Tpoint b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));} inline double det(Tpoint p0,Tpoint p1,Tpoint p2){return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);} int N; Tpoint square[maxN+100][2]; Tpoint a[maxN+100][2]; int id[maxN+100][2],cnt; int now,info[2*maxN+100]; struct Tedge{int v,next;double dis;}edge[2*maxN*2*maxN+1000]; double ans,v; Tpoint S,T; int eS,eT,idS,idT; inline void addedge(int u,int v,double dis) { now++; edge[now].v=v; edge[now].dis=abs(dis); edge[now].next=info[u]; info[u]=now; } inline void solve(Tpoint s,int num,int l) { if (num!=idS && num!=idT && num%2==0){addedge(num,num+1,dis(a[l][0],a[l][1]));addedge(num+1,num,dis(a[l][0],a[l][1]));} Tpoint low,high,t1,t2;bool flag=0; for(int i=l-1;i>=1;i--) { if (!flag && (id[i][0]==idS || id[i][0]==idT)) { addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0])); continue; } if (!flag) { addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0])); addedge(num,id[i][1],dis(s,a[i][1]));addedge(id[i][1],num,dis(s,a[i][1])); low=a[i][0]; high=a[i][1]; flag=1; continue; } t1=a[i][0];t2=a[i][1]; if ( dblcmp(det(s,low,t1))<=0 && dblcmp(det(s,high,t1))>=0 ){addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0]));} if ( dblcmp(det(s,low,t2))<=0 && dblcmp(det(s,high,t2))>=0 ){addedge(num,id[i][1],dis(s,a[i][1]));addedge(id[i][1],num,dis(s,a[i][1]));} if (id[i][0]!=idS && id[i][0]!=idT) { if ( dblcmp( det(s,low,t2) ) == 1 ) break; if ( dblcmp( det(s,high,t1)) == -1 ) break; if ( dblcmp( det(s,low,t1) ) == -1 ) low=t1; if ( dblcmp( det(s,high,t2))== 1 ) high=t2; } } } int head,tail,queue[7*2*maxN+100]; bool vis[2*maxN+100]; double f[2*maxN+100]; inline double SPFA() { int S=idS,T=idT; for(int i=1;i<=cnt;i++) f[i]=INF; queue[head=tail=0]=S; f[S]=0.0;vis[S]=1; while(head<=tail) { int u=queue[(head++)%(7*2*maxN+100)],v,i;double dis; vis[u]=0; for(i=info[u],v=edge[i].v,dis=edge[i].dis;i!=-1;i=edge[i].next,v=edge[i].v,dis=edge[i].dis) if ( dblcmp(dis+f[u]-f[v])==-1 ) { f[v]=dis+f[u]; if (!vis[v]) { vis[v]=1; queue[(++tail)%(7*2*maxN+100)]=v; if ( dblcmp(f[queue[head%(7*2*maxN+100)]]-f[queue[tail%(7*2*maxN+100)]])==1 ) swap(queue[tail%(7*2*maxN+100)],queue[head%(7*2*maxN+100)]); } } } return abs(f[T]); } int main() { freopen("car.in","r",stdin); freopen("car.out","w",stdout); scanf("%d ",&N); for(int i=1;i<=N;i++)scanf("%lf%lf%lf%lf ",&square[i][0].x,&square[i][0].y,&square[i][1].x,&square[i][1].y); scanf("%lf%lf ",&S.x,&S.y); for(int i=1;i<=N;i++) if (dblcmp(square[i][0].x-S.x)<=0 && dblcmp(S.x-square[i][1].x)<=0 && dblcmp(square[i][0].y-S.y)<=0 && dblcmp(S.y-square[i][1].y)<=0){eS=i;break;} scanf("%lf%lf ",&T.x,&T.y); for(int i=1;i<=N;i++) if (dblcmp(square[i][0].x-T.x)<=0 && dblcmp(T.x-square[i][1].x)<=0 && dblcmp(square[i][0].y-T.y)<=0 && dblcmp(T.y-square[i][1].y)<=0){eT=i;break;} int g=N;N=0; for(int i=1;i<=g;i++) { if (i==eS) { N++; a[N][0].x=S.x;a[N][0].y=S.y; a[N][1].x=S.x;a[N][1].y=S.y; idS=id[N][0]=id[N][1]=++cnt; } if (i==eT) { N++; a[N][0].x=T.x;a[N][0].y=T.y; a[N][1].x=T.x;a[N][1].y=T.y; idT=id[N][0]=id[N][1]=++cnt; } if (i==g) continue; N++; a[N][0].x=square[i][1].x;a[N][0].y=max(square[i][0].y,square[i+1][0].y); a[N][1].x=square[i][1].x;a[N][1].y=min(square[i][1].y,square[i+1][1].y); id[N][0]=++cnt;id[N][1]=++cnt; } memset(info,-1,sizeof(info));now=-1; for(int i=2;i<=N;i++) for(int j=0;j<2;j++) solve(a[i][j],id[i][j],i); ans=SPFA(); scanf("%lf ",&v); ans=ans/v; printf("%0.10lf ",ans); return 0; }