用户工具

站点工具


2020-2021:teams:intrepidsword:petrozavodsk-summer-2015

Practice link

Solutions

B. Break Free

题目大意:一个人在 $(x,y)(y>0)$,他要走到 $x$ 轴上 $[0,a](a>0)$ 这个区间上某一点。他必须以 $v$ 的速度匀速直线运动。另外有 $m$ 只老虎,每只位于 $(x_{i},y_{i})(y_{i}\ge0)$,老虎可以以不超过 $u_{i}$ 的速度,向任意方向运动。问 $x$ 轴上安全的点集的测度。安全的点是指走到这个点不会被老虎吃掉。

题解:显然每只老虎分别考虑。若 $u\ge v$,那么如果老虎在中途能吃掉这个人,那么显然可以继续跟着他走到 $x$ 轴。所以实质上就是判断 $x$ 轴上每个点,人走到它的时间和老虎走到它的时间哪个长。可以发现这是一个二次不等式,就不赘述了。

若 $u<v$,那么有可能老虎只有在中间一段才能吃到人。设人与老虎之间的距离为 $d$,人行走的方向与人与老虎之间的连线成 $\theta$ 角。考虑余弦定理:

$$ \begin{aligned} v^{2}t^{2}+d^{2}-2vtd\cos\theta&\le u^{2}t^{2}\\ (v^{2}-u^{2})t^{2}+d^{2}-2vtd\cos\theta&\le0 \end{aligned} $$

那么首先就可以得出,要使不等式有解,判别式要大于等于 $0$。但是仅有解还不够,需要在人到达终点前有解。考虑该二次函数在 $t=\frac{vd\cos\theta}{v^{2}-u^{2}}$ 处取得最小值。那么人运动的距离为 $\frac{v^{2}d\cos\theta}{v^{2}-u^{2}}$,观察可得,它的轨迹是一个圆(一条直径是从人出发,指向老虎,长度为 $\frac{v^{2}d}{v^{2}-u^{2}}$)。那么终点线段在圆外的部分,老虎一定可以抓到。在圆内的部分,容易发现也是有解等于线段上有解,同上一部分。

2020-2021/teams/intrepidsword/petrozavodsk-summer-2015.txt · 最后更改: 2021/06/20 20:57 由 toxel