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

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:petrozavodsk-summer-2015 [2021/06/14 13:30]
toxel 创建
+++ 2020-2021:teams:intrepidsword:petrozavodsk-summer-2015 [2021/06/20 20:57] (当前版本)
toxel
@@ 行 1: / 行 1: @@
 [[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001469|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.1623648618.txt.gz · 最后更改: 2021/06/14 13:30 由 toxel