题解 P4498 [WC2007] 疯狂赛车

Vamper · 2021-03-26 21:37:33 · 题解

题目大意：

给定 n 个点，连边和空地上的速度不同，求从原点到第n个点的最短时间

分析

根据光路最短原理（即平稳时间定理）结合斯涅尔定理可知，直接走公路走到第 n 个点是肯定不可行滴

插一张图解释一下，对于光线来说，从介质1到介质2之间速度大小会发生变化，由此会产生一个偏转角 \theta

有公式：\frac{sin\theta_{1}}{sin\theta_{2}}=n_{21} (sin\theta_{1}\times n_{1}=sin\theta_{2}\times n{2})

式中 n_{21} 称为第二介质对第一介质的相对折射率。

但其实，知道这个东西也没有什么意义

下面开始本题真正的推导

从 A\rightarrow C 有两条路径，现在根据光路最短原理，显然是 A\rightarrow B\rightarrow C 这条路径较短

则这条路径所需时间为：

对 t 求导，则：

令 t^{'}=0 ，解得 v_2=cos\theta v_1 ，即 cos\theta=\frac{v_b}{v_a}

那么现在的问题就转化为了如何求这个点

考虑相邻的两个点之间一定是走公路最短，但因为题目说可以走回头路，所以就有了我们可以先到下一个点，在回到这一个点去另外一个点的这种情况

所以这个偏转点一定不在相邻的两个点间

考虑如何 O(1) 的求这个点，利用向量可以非常轻易地做到这件事，我们构造两条过点 P 的直线(设偏转点为 P )

举个例子怎么求：

已知向量 AB 和向量 CD

向量 AP=(x+1,y+1)，向量 BP=(x-2,y-3)

向量 CP=(x-1,y+2)，向量 DP=(x+2,y-4)

得到 x=-\frac{1}{10}，y=\frac{1}{5}

所以首先建立一个向量库，重载向量的坐标加，坐标减，坐标数乘，坐标数量积

struct Point {
    db x,y;

    Point() {}

    Point(db x,db y) : x(x),y(y) {};

    friend Point operator + (Point a,Point b) {
        return Point(a.x+b.x,a.y+b.y);
    }

    friend Point operator - (Point a,Point b) {
        return Point(a.x-b.x,a.y-b.y);
    }

    friend Point operator * (Point a,db b) {
        return Point(a.x*b,a.y*b);
    }

    friend Point operator / (Point a,db b) {
        return Point(a.x/b,a.y/b);
    }

    friend db operator * (Point a,Point b) {
        return a.x*b.x+a.y*b.y;
    }

    friend bool operator == (Point a,Point b) {
        return !sgn(a.x-b.x)&&!sgn(a.y-b.y);
    }

    db len() {
        return hypot(x,y);
    }

    Point rotate(db s,db c) {
        return Point(x*c-y*s,x*s+y*c);
    }

    Point rotate_90() {
        return Point(-y,x);
    }

};

rotate 的作用：我们将原点到这个点的向量绕原点顺时针旋转\theta，将过 P 的两个向量映射到 x 轴上求出 \frac{AP}{AB} （设 P 在 AB 上）然后就可以得到 P 的坐标

//求点
void work(int st,int en) {
    int cot=2;
    Point A=a[st],B=a[en],C=(B-A).rotate_90();
    e[1]=E(0,st),e[2]=E(C.len(),en);
    FOR(i,0,n) {
        if(i==st||i==en) continue;
        FOR(j,0,1) {
            Point D=line_intersection(A,B,a[i],a[i]+C.rotate(s[j],c[j]));
            if(D==A||D==B) continue;
            if(!point_on_segment(D,A,B)) continue;
            cnt++;
            add_edge(i,cnt,(a[i]-D).len()/vb);
            e[++cot]=E((D-A).len(),cnt);
        }
    }
    sort(e+1,e+cot+1);
    FOR(i,1,cot-1) add_edge(e[i].y,e[i+1].y,(e[i+1].x-e[i].x)/va);
}

求得每两个点之间的 P 点以后，连边，将 P 与剩下的每个点连边，以时间作为边权，跑 Dijkstra 即可

至此完整代码就很容易得出了，但是细节有亿点点多……

AC\ Code

#include<bits/stdc++.h>
#define re register
#define db double
#define pr pair<db,int>
#define mp make_pair
#define sgn(x) (x>1e-6?1:(x<-1e-6?-1:0))
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;i++)
#define REP(u) for(re int i=head[u];i;i=edge[i].nxt)
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 2010
using namespace std;

const db esp=1e-6;
const db INF=1e100;

struct Point {
    db x,y;

    Point() {}

    Point(db x,db y) : x(x),y(y) {};

    friend Point operator + (Point a,Point b) {
        return Point(a.x+b.x,a.y+b.y);
    }

    friend Point operator - (Point a,Point b) {
        return Point(a.x-b.x,a.y-b.y);
    }

    friend Point operator * (Point a,db b) {
        return Point(a.x*b,a.y*b);
    }

    friend Point operator / (Point a,db b) {
        return Point(a.x/b,a.y/b);
    }

    friend db operator * (Point a,Point b) {
        return a.x*b.x+a.y*b.y;
    }

    friend bool operator == (Point a,Point b) {
        return !sgn(a.x-b.x)&&!sgn(a.y-b.y);
    }

    db len() {
        return hypot(x,y);
    }

    Point rotate(db s,db c) {
        return Point(x*c-y*s,x*s+y*c);
    }

    Point rotate_90() {
        return Point(-y,x);
    }

};

struct Edge {
    int v,nxt;
    db w;
    Edge() {}
    Edge(int v,int nxt,db w) : v(v),nxt(nxt),w(w) {};
};

struct E {
    db x;
    int y;
    E() {}
    E(db x,int y): x(x),y(y) {};
    bool operator < (const E& b) const {
        return x<b.x;
    }
};

int n;
db va,vb;
db s[2],c[2],d[2100000];
int head[2100000],tot;
int cnt;

Point a[N];
Edge edge[9100000];
E e[N];

priority_queue<pr,vector<pr>,greater<pr> > q;

void add_edge(int u,int v,db w);
void work(int st,int en);
Point line_intersection(Point a,Point b,Point p,Point q);
bool point_on_segment(Point p,Point a,Point b);
void judge_ext(int x,db y);

int main() {
    cin>>n>>va>>vb;
    FOR(i,1,n) cin>>a[i].x>>a[i].y;
    //特判
    if(sgn(va-vb)<=0) return printf("%.10lf",(a[0]-a[n]).len()/vb),0;
    //光路最短原理
    s[0]=vb/va,c[0]=sqrt(1-s[0]*s[0]);
   //此处sin和cos写反了，所以后面有一个rotate_90
    s[1]=-s[0],c[1]=c[0];
    cnt=n;
    FOR(i,0,n) FOR(j,0,i-1) add_edge(i,j,(a[i]-a[j]).len()/vb);
    //建边
    FOR(i,0,n-1) work(i,i+1);
    FOR(i,0,cnt) d[i]=INF;
    judge_ext(0,0);
    while(!q.empty()) {
        pr t=q.top();
        q.pop();
        if(t.first-esp>d[t.second]) continue;
        int u=t.second;
        REP(u) judge_ext(edge[i].v,t.first+edge[i].w);
    }
    printf("%.10lf",d[n]);
    return 0;
}

void add_edge(int u,int v,db w) {
    edge[++tot]=(Edge) {v,head[u],w},head[u]=tot;
    edge[++tot]=(Edge) {u,head[v],w},head[v]=tot;
}

db cross(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}

void work(int st,int en) {
    int cot=2;
    Point A=a[st],B=a[en],C=(B-A).rotate_90();
    e[1]=E(0,st),e[2]=E(C.len(),en);
    FOR(i,0,n) {
        if(i==st||i==en) continue;
        FOR(j,0,1) {
            Point D=line_intersection(A,B,a[i],a[i]+C.rotate(s[j],c[j]));
            if(D==A||D==B) continue;
            if(!point_on_segment(D,A,B)) continue;
            cnt++;
            add_edge(i,cnt,(a[i]-D).len()/vb);
            e[++cot]=E((D-A).len(),cnt);
        }
    }
    sort(e+1,e+cot+1);
    FOR(i,1,cot-1) add_edge(e[i].y,e[i+1].y,(e[i+1].x-e[i].x)/va);
}

//计算交点
Point line_intersection(Point a,Point b,Point p,Point q) {
    db U=cross(p-a,q-p),D=cross(b-a,q-p);
    return a+(b-a)*(U/D);
}

//判断D点是否在AB这条线段上
bool point_on_segment(Point p,Point a,Point b) {
    return sgn(cross(b-a,p-a))==0&&sgn((p-a)*(p-b))<=0;
}

void judge_ext(int x,db y) {
    if(y+esp<d[x]) q.push(mp(d[x]=y,x));
}