CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[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}}$）。那么终点线段在圆外的部分，老虎一定可以抓到。在圆内的部分，容易发现也是有解等于线段上有解，同上一部分。
CVBB ACM Team

用户工具

站点工具

页面工具
