即将 AFO 的老年选手

题解 P6945 【[ICPC2018 WF]Getting a Jump on Crime】

2021-01-02 09:06:33


广告

如果我们能够求出从 $u$ 能否到达 $v$,那么就变成一个简单的最短路了,直接 BFS 即可。

考虑这个东西怎么求。设距离为 $d$,高度差为 $h$,根据物理必修一相关知识,可以列出方程

$$\begin{cases}v_x\!^2+v_y\!^2=v^2\\d=v_xt\\v_yt-\frac{1}{2}gt^2=h\end{cases}$$

化简得到

$$\frac{1}{4}g^2t^4+(gh-v^2)t^2+h^2+d^2=0$$

我们肯定想让 $v_y$ 尽量大(这样就更不容易撞到楼上),所以我们只需要求出 $t$ 的最大值,从而求出 $v_x,v_y$。

然后我们枚举每个边界,如果和路线有交的话就算出跳到这个位置时的高度,然后比较一下即可知道是否会撞上。

代码写得很丑就不放了。