ICPC D.Walker

题目链接
思路
一共分三种情况
1.一个人走完所有的路
2.两个人交叉走完所有的路
3. 两个人各负责自己的一边，然后在中间相遇，那么对于每个人，有两种选择，一种是先往端点走，一种是先往中间走，那么我们可以二分走到中间点的位置，就能够算出每个人往中间最多能走多少时间，判断一下左右所用时间大小就饿可以了
代码

#include <bits/stdc++.h>

//#define min(a,b,c) min(a,min(b,c))

using namespace std;

const double eps = 1e-8;

int main()
{
    int _; cin >> _;
    while(_ --){
        double n,p1,v1,p2,v2;
        cin >> n >> p1 >> v1 >> p2 >> v2;
        
        if(p1 > p2){
            swap(p1,p2);
            swap(v1,v2);
        }
        
        double ans =  1e20;
        
        // 一个人走完所有路程
        ans = min(ans, min(p1 + n, n + n - p1) / v1);
        ans = min(ans, min(n - p2 + n ,  p2 + n) / v2);
        
        // 两个人交叉走完对方的路程
        ans = min(ans, max((n - p1) / v1, p2 / v2));
        
        // 两个人各走各的
        double l = p1, r = p2;
        while(r - l > eps){
            double mid = (l + r) / 2;
            
            double lt = min(mid + p1 , mid + mid - p1) / v1;
            double rt = min(n - mid + n - p2, p2 - mid + n - mid) / v2;
            ans = min(ans,max(lt,rt));
            
            if(lt <= rt) l = mid; // 如果左边用的时间少于右边用的那就说明二分的点靠左了
            else r = mid;
        }
        printf("%.8f\n",ans);
    }
}

ICPC D.Walker

原文：https://www.cnblogs.com/acm-Patrick/p/14156938.html