C++(clang++11) 解法, 执行用时: 34ms, 内存消耗: 492K, 提交时间: 2022-08-15 08:56:23

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cmath>
using namespace std;
int a[10],n,stx,sty,edx,edy,num;
int x1[2010],ydown[2010],x2[2010],y2[2010];
double v,dis[4010];
struct node{
    int x;int y;
}p[5005];
void saw()
{
    num=1;p[1].x=stx;p[1].y=sty;
    for (int i=1;i<n;i++)
    {
        if (stx>x2[i]) continue;    
        if (x2[i]>edx) break;
        a[1]=ydown[i],a[2]=y2[i],a[3]=ydown[i+1],a[4]=y2[i+1];
        sort(a+1,a+1+4);
        num++;
        p[num].x=x2[i];
        p[num].y=a[2];
        num++;
        p[num].x=x2[i];
        p[num].y=a[3];
    }
    num++;
    p[num].x=edx;
    p[num].y=edy;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) 
    scanf("%d%d%d%d",&x1[i],&ydown[i],&x2[i],&y2[i]);
    scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
    if (stx>edx) 
    {
        swap(stx,edx);
        swap(sty,edy);
    }
    scanf("%lf",&v);    
    saw();
    for (int i=2;i<=num;i++) dis[i]=1e99;
    for (int i=1;i<num;i++)
    {
        double nox=(double)p[i].x*1.0;
        double noy=(double)p[i].y*1.0;
        double mmax=1e99;
        double mmin=-1e99;
        for (int j=i+1;j<=num;j++)
        {
            double len;
            double nex=(double)p[j].x*1.0;
            double ney=(double)p[j].y*1.0;

            if (nex==nox)
            {
                len=abs(ney-noy);
                dis[j]=min(dis[j],len+dis[i]);
                continue;
            }
            double tmp=(ney-noy)/(nex-nox);
            if ((tmp<=mmax)&&(tmp>=mmin))
            {
                double hh=(ney-noy)*(ney-noy)+(nex-nox)*(nex-nox);
                len=sqrt(hh);
                dis[j]=min(dis[j],len+dis[i]);
            }
            if ((j%2)==0)   mmin=max(mmin,tmp);
            else    mmax=min(mmax,tmp);
        }
    }
    double ans=dis[num]/v;
    printf("%.10lf\n",ans);
}