JLOI2010 铁人双项比赛

我们有一个式子

t_i=\frac{k\left( v_{2i}-v_{1i} \right)}{v_{1i}v_{2i}}+\frac{s}{v_{2i}}

然后把 k 看做 x 轴,把 t 看作 y 轴,就是 n 条直线。

嗯,对于前 n-1 条求半平面交(注意直线对应的半平面是右侧)。

对于最后一条直线,最优的 k 是与这个凸包相切的时候。

而且显然 k 只会在端点处取到,所以直接二分找到斜率最近似的直线然后算一下答案即可。

注意最优的 k 为负的时候要调整为 0 并判定是否有解。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据