一开始看这道题,感觉是个水题……
显然,我们只用考虑每次离开一个矩形时的y坐标。如果我们离开一个矩形时,走的是相邻两矩形相交的那条线段,我们称其为一次“关键通过”,通过点称为“关键点”。那么一次通过,要么走一个前面的关键点和后面一个关键点,离开点连线交点,要么“关键通过”该矩形。
如果起点的x坐标比较大,就交换一下起点终点。
动态规划,记f[i][0]表示从可通过线段的最低点离开矩形i,记f[i][1]表示从最高点通过矩形i。每次枚举上一个“关键通过”的矩形(或者从前往后转移,枚举下一个“关键通过”的矩形)进行转移,最后考虑第一个和最后一个被“关键通过”的矩形,然后从起点走到第一个关键点,从最后一个关键点走到终点。
那么如何判断能否直接从一个关键点走到另一个呢?在起点固定的情况下,我们的直线行走路径的斜率会被限制在一个区间里,那么直接在枚举下一个点的过程中(或固定终点,枚举上一个点),不断更新合法斜率区间,来判断当前这个转移是否合法。复杂度就是$O(n^2)$的。
美滋滋……?诶,怎么WA啦。
然后我就找了很多已经通过的程序来对拍,结果没把自己拍出多少错,倒是把跟我对拍的四款程序都拍出WA来了。
最后面向数据调试才解决……有以下坑点:
1.起点和第一个关键点,终点和最后一个关键点,起点和终点的横坐标相同,要特判。并且还要注意这个相同还分起点/终点夹在通过线段中间的情况和起点终点在通过线段一侧的情况。
2.没有关键点,起点直接走到终点的情况。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
const int N=2002;
const db inf=1e11,eps=1e-9;
int n,sx,sy,ex,ey,sb,eb;db V,ans;
int X1[N],X2[N],Y1[N],Y2[N],L[N],R[N];db f[N][2];
db getk(db xx1,db yy1,db xx2,db yy2) {return (yy2-yy1)/(xx2-xx1);}
db dist(db xx1,db yy1,db xx2,db yy2)
    {return sqrt((xx1-xx2)*(xx1-xx2)+(yy1-yy2)*(yy1-yy2));}
void work() {
    if(sx==ex) {printf("%.8lf\n",dist(sx,sy,ex,ey)/V);return;}//起点终点横坐标相同
    for(RI i=1;i<=n;++i) f[i][0]=f[i][1]=inf;
    for(RI i=1;i<n;++i) L[i]=max(Y1[i],Y1[i+1]),R[i]=min(Y2[i],Y2[i+1]);
    db kl=-inf,kr=inf;ans=inf;
    for(RI i=sb;i<eb;++i) {
        if(i==sb&&sx==X2[i]) {//起点和第一个关键点横坐标相同
            f[i][0]=dist(sx,sy,X2[i],L[i]);
            f[i][1]=dist(sx,sy,X2[i],R[i]);
            if(sy<Y1[i]||sy>Y2[i]) {kl=inf,kr=-inf;break;}
        }
        db ll=getk(sx,sy,X2[i],L[i]),rr=getk(sx,sy,X2[i],R[i]);
        if(kl<ll+eps&&kr+eps>ll) f[i][0]=dist(sx,sy,X2[i],L[i]);
        if(kl<rr+eps&&kr+eps>rr) f[i][1]=dist(sx,sy,X2[i],R[i]);
        kl=max(kl,ll),kr=min(kr,rr);
    }
    db kk=getk(sx,sy,ex,ey);
    if(kl<kk+eps&&kr+eps>kk) ans=dist(sx,sy,ex,ey);
    for(RI i=sb;i<eb;++i) {
        db kl1=-inf,kr1=inf,kl2=-inf,kr2=inf;
        for(RI j=i+1;j<eb;++j) {
            db ll=getk(X2[i],L[i],X2[j],L[j]),rr=getk(X2[i],L[i],X2[j],R[j]);
            if(kl1<ll+eps&&kr1+eps>ll)
                f[j][0]=min(f[i][0]+dist(X2[i],L[i],X2[j],L[j]),f[j][0]);
            if(kl1<rr+eps&&kr1+eps>rr)
                f[j][1]=min(f[i][0]+dist(X2[i],L[i],X2[j],R[j]),f[j][1]);
            kl1=max(kl1,ll),kr1=min(kr1,rr);
            ll=getk(X2[i],R[i],X2[j],L[j]),rr=getk(X2[i],R[i],X2[j],R[j]);
            if(kl2<ll+eps&&kr2+eps>ll)
                f[j][0]=min(f[i][1]+dist(X2[i],R[i],X2[j],L[j]),f[j][0]);
            if(kl2<rr+eps&&kr2+eps>rr)
                f[j][1]=min(f[i][1]+dist(X2[i],R[i],X2[j],R[j]),f[j][1]);
            kl2=max(kl2,ll),kr2=min(kr2,rr);
        }
        if(i==eb-1&&ex==X1[eb]) {//终点和最后一个关键点横坐标相同
            if(ey<Y1[eb]||ey>Y2[eb]) continue;
            ans=min(ans,f[i][0]+dist(X2[i],L[i],ex,ey));
            ans=min(ans,f[i][1]+dist(X2[i],R[i],ex,ey));
            continue;
        }
        db ll=getk(X2[i],L[i],ex,ey),rr=getk(X2[i],R[i],ex,ey);
        if(kl1<ll+eps&&kr1+eps>ll)
            ans=min(ans,f[i][0]+dist(X2[i],L[i],ex,ey));
        if(kl2<rr+eps&&kr2+eps>ll)
            ans=min(ans,f[i][1]+dist(X2[i],R[i],ex,ey));
    }
    printf("%.8lf\n",ans/V);
}
int main()
{
    scanf("%d",&n);
    for(RI i=1;i<=n;++i)
        scanf("%d%d%d%d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    if(sx>ex) swap(sx,ex),swap(sy,ey);
    scanf("%lf",&V);
    sb=eb=1;
    for(RI i=n;i>=1;--i) {
        if(X1[i]<=sx&&X2[i]>=sx&&Y1[i]<=sy&&Y2[i]>=sy) sb=i;
        if(X1[i]<=ex&&X2[i]>=ex&&Y1[i]<=ey&&Y2[i]>=ey) eb=i;
    }
    work();
    return 0;
}

鉴于本题还挺难调的,放出(只能生成弱逼数据的)数据生成器代码:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
int X1[100],Y1[100],X2[100],Y2[100],xx[100];
int main()
{
    srand(time(0));
    int n=rand()%4+1;
    printf("%d\n",n);
    for(RI i=1;i<=n+1;++i) xx[i]=xx[i-1]+rand()%3+1;
    sort(xx+1,xx+2+n);
    X2[0]=xx[1];for(RI i=1;i<=n;++i) X1[i]=X2[i-1],X2[i]=xx[i+1];
    Y2[1]=rand()%8+1,Y1[1]=Y2[1]-rand()%3-1;
    for(RI i=2;i<=n;++i) {
        Y2[i]=rand()%4+Y1[i-1]+1;
        Y1[i]=min(Y2[i],Y2[i-1])-rand()%4-1;
    }
    for(RI i=1;i<=n;++i) printf("%d %d %d %d\n",X1[i],Y1[i],X2[i],Y2[i]);
    int sx=rand()%xx[n+1]+1,ex=rand()%xx[n+1]+1;
    int sb=1,eb=1;
    for(RI i=1;i<=n;++i) {
        if(X1[i]<sx&&X2[i]>=sx) sb=i;
        if(X1[i]<ex&&X2[i]>=ex) eb=i;
    }
    int sy=rand()%(Y2[sb]-Y1[sb]+1)+Y1[sb];
    int ey=rand()%(Y2[eb]-Y1[eb]+1)+Y1[eb];
    printf("%d %d %d %d\n",sx,sy,ex,ey);
    puts("1.00");
    return 0;
}

最后追加几组数据……大家也可以用来测测自己的代码。

3
2 -1 3 2
3 0 4 1
4 -3 7 3
3 2 6 2
1.00

答案是4.23606798

2
3 6 6 7
6 4 7 9
5 7
7 7
1.00

答案是2.00000000

3
1 4 2 6
2 2 3 6
3 2 4 4
2 6
3 5
1.00

答案是1.41421356

2
2 6 4 8
4 5 6 7
4 8
3 6
1.0

答案是2.23606798

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *