第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）D.Walker（二分）

分析

我们可以发现总共可以分一下情况：

1. 一个人走完全程
2. 两个人交叉走（不回头）
3. 一个人走一部分，路径不交叉

前两种情况我们可以直接算出来，后面的一种我们要将路程分为两段，一段 p1 跑，一段 p2 跑，两个人跑完的时间越接近，情况越优。所以我们可以二分分割点（肯定在 p1 和 p2 之间）。

代码

#include<bits/stdc++.h>
using namespace std;double n,p1,v1,p2,v2;
double eps = 1e-8;void solve()
{
    cin>>n>>p1>>v1>>p2>>v2;if(p1 > p2) swap(p1, p2), swap(v1, v2);double ans = (p1 + n) / v1;//单人走完全程 ans = min(ans, (2.0 * n - p1) / v1);ans = min(ans, (p2 + n) / v2);ans = min(ans, (2.0 * n - p2) / v2);ans = min(ans, max(p2 / v2, (n - p1) / v1));//两人交叉走 double l = p1, r = p2;while(r - l > eps){
    double mid = (l + r) / 2.0;double t1 = min(2.0 * mid - p1, p1 + mid) / v1;double t2 = min(n - mid + p2 - mid, n - mid + n - p2) / v2;ans = min(ans, max(t1, t2));if(t1 > t2) r = mid;else l = mid;}printf("%.10lf\n",ans);
}int main()
{
    int T;cin>>T;while(T--){
    solve();}return 0;
}