链接：https://ac.nowcoder.com/acm/contest/9925/D
来源：牛客网
题目描述
As a world-famous traveler, Prof. Pang's research interest is to travel as many places as possible in his life.
We have a segment [0,n][0,n]. There are two travelers on it. The first one is on position p1p1 with velocity v1v1(which means s/he can walk v1v1 unit on the segment per second). The second one is on position p2p2 with velocity v2v2.
From their respective beginning points, travelers can walk on the segment. They cannot walk outside the segment. Whenever they want to change their direction, they can turn around immediately.
Please help Prof. Pang to calculate the minimum possible time by which every position of the segment is passed by at least one traveler.
输入描述:
The first line contains one integer test (1≤test≤10000)test (1≤test≤10000) -- the number of test cases.
The i-th of the next test lines contains five numbers n,p1,i,v1,i,p2,i,v2,in,p1,i,v1,i,p2,i,v2,i (0<n≤100000<n≤10000, 0≤p1,i,p2,i≤n0≤p1,i,p2,i≤n, 0.001≤v1,i,v2,i≤10000.001≤v1,i,v2,i≤1000). All numbers have at most 3 digits after the decimal point.
输出描述:
For each test case, we should output one number -- the minimum time that every position of the segment is passed by at least one traveler.
Your answer is considered correct if its absolute or relative error does not exceed 10−610−6.
示例1
输入
复制
2
10000.0 1.0 0.001 9999.0 0.001
4306.063 4079.874 0.607 1033.423 0.847
输出
复制
5001000.0000000000
3827.8370013755
讨论了半天一直wa...然后看了高中同学的两个队的代码，一个分了十好几种情况.....一个用的二分
不妨假定p1小于p2，首先可以算出几种情况：
p1朝右走到头，p2朝左走到头，取max
p1自己走（先向右走到头再向左走完全程 or 先向左走到头再向右走完全程）
p2自己走（先向右走到头再向左走完全程 or 先向左走到头再向右走完全程）
这几种情况对于时间取一个最小值，然后分析两者都折返的情况：
我们不妨让p1走左半部分，p2走右半部分，然后二分这两段的分界点，二分的界是[p1, p2]。至于为什么是[p1, p2]，可以知道比如mid大于p2的话，p1先向左到头走再走到mid，p2向右走到头再走到mid，但其实p1再向右走的时候根本没必要走到mid，p2也没必要再折返到mid，这实际上等价于mid是p2的情况，因此诸如此类的状态是没有意义的。
然后二分时对于每次mid，p1有两种走法（先向左再向右和先向右再向左，最终都是把mid左边的线段覆盖），这样可以求出来一个最小时间t1，同理p2可以求出t2，如果t1小于t2就把mid右移，反之左移，然后更新ans。
#include <iostream>
using namespace std;
double n, p1, v1, p2, v2, ans;
int main()
{
freopen("data.txt", "r", stdin);
int t;
cin >> t;
while(t--)
{
ans = 1e18;
cin >> n >> p1 >> v1 >> p2 >> v2;
if(p1 > p2)
{
swap(p1, p2);
swap(v1, v2);
}
ans = min(ans, max(p2 / v2, (n - p1) / v1));//p1朝右走到头 p2朝左走到头
ans = min(ans, min((p1 + n) / v1, (2 * n - p1) / v1));
ans = min(ans, min((2 * n - p2) / v2, (p2 + n) / v2));
double l = 0, r = n, mid;
for(int i = 1; i <= 100; i++)
{
mid = (l + r) / 2.0;
double t1 = min((mid + p1) / v1, (mid + mid - p1) / v1);
double t2 = min((2.0 * n - mid - p2) / v2, 1.0 * (n - mid + p2 - mid) / v2);
ans = min(ans, max(t1, t2));
if(t1 > t2) r = mid;
else l = mid;
}
printf("%.10lf
", ans);
}
return 0;
}