【题解】bzoj2433/洛谷 P1995/loj2443 智能车比赛 计算几何+DP ——by litble

一开始看这道题，感觉是个水题……
显然，我们只用考虑每次离开一个矩形时的 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