Codeforces #364 C. Chris and Road

正文索引 [隐藏]

传送门:http://www.codeforces.com/contest/703/problem/C

题目翻译

一个凸多边形在初始给定的位置以恒定V的速度
在原点有个行人以最大u的速度上行
问行人最快到达(0,w)的时间
行人不能被凸多边形撞(行人点与凸多边形边重合不算被撞,只有行人进入凸多边形内部才算被撞)

题解

我们只需要考虑行人一开始冲过去和等车子过了之后再过两种情况。
对于每个凸多边形上的点,当它到达y轴时行人已经可以走到它的位置或更高,那么行人就不会被撞,如果所有点都满足即可直接冲过去。
如果不能冲,从低往高枚举凸多边形的点,计算尽量贴着凸多边形走/以全速搜的情况,就是答案。

代码