20 years' Shanghai station D question Walker (two points, concise)

Title Description

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]}[0,n]. There are two travelers on it. The first one is on position p1p_1p1​ with velocity v1v_1v1​ (which means s/he can walk v1v_1v1​ unit on the segment per second). The second one is on position p2p_2p2​ with velocity v2v_2v2​.

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.

Input description :

The first line contains one integer test (1≤test≤10000)test~(1\le test\le 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, p_{1, i}, v_{1, i}, p_{2, i}, v_{2, i}n,p1,i​,v1,i​,p2,i​,v2,i​ (0<n≤100000 < n \le 100000<n≤10000, 0≤p1,i,p2,i≤n0\le p_{1, i},p_{2, i} \le n0≤p1,i​,p2,i​≤n, 0.001≤v1,i,v2,i≤10000.001 \le v_{1, i},v_{2, i} \le 10000.001≤v1,i​,v2,i​≤1000). All numbers have at most 3 digits after the decimal point.

Output description :

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}10−6.

Input

2
10000.0 1.0 0.001 9999.0 0.001
4306.063 4079.874 0.607 1033.423 0.847

Output

5001000.0000000000
3827.8370013755

The question ：0-n On one-dimensional coordinates of , Give the position and velocity of any two points , They can go in any direction at any time , Ask these two points to complete all the places together in the least time .

Ideas ：

First, judge whether the previous position is smaller , No. swap Turn it over , The front one is a, The back is b

It's not particularly difficult to do questions , There are four situations ：

1. Only a perhaps b, The answer is ：(x+min(a.x,x-a.x))/a.v, and (x+min(b.x,x-b.x))/b.v), because a perhaps b You can choose whether to reach the left endpoint first or the right endpoint

2.a and b Cross walk , And cross and go straight . The answer is ：max(b.x/b.v,(x-a.x)/a.v), The maximum usage time is the answer .

The picture taken next door , Invasion and deletion

3. Left by a Come and go , Right by b Come and go . The middle point is mid, be mid It must be a and b Between starting points , Because once a Right past b The starting point , that b You don't have to go to the right ,b It's useless. , It belongs to the first case .

Invasion and deletion

  This is mid On the left is a Come and go , On the right is b Come and go

a The shortest path is ：mid+min(a.x,mid-a.x)

b The shortest path is ：l-mid+min(n-b.x,b.x-mid)

And the answer to decimals , The maximum on both sides is the answer , It must be the best when the left and right use time are the same , This process can be divided into two .

There is another important point about this question , It's about precision , So that some of the questions have 100 Second half for

But like my code below , No, long double, No, 1e-10, No multi decimal output

The precision card of this question is the result returned by the dichotomy ：return max(l/a.v+(min(a.x,l-a.x))/a.v,((x-l)+min(x-b.x,b.x-l))/b.v);

It must be max（） Of , You cannot return only one , This depends on the code specification .

Code ：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define dou double
#define EXP 0.0000001
#define M 1000005
int T;
dou x;
struct Node{
    dou x,v;
}a,b;
bool check(dou mid){
    return (mid+min(a.x,mid-a.x))/a.v>((x-mid)+min(x-b.x,b.x-mid))/b.v;
}
dou solve(){
    dou l=a.x,r=b.x;
    while(r-l>EXP){
        dou mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    return max(l/a.v+(min(a.x,l-a.x))/a.v,((x-l)+min(x-b.x,b.x-l))/b.v);        // This must be max, Returning only the left time or the right time will WA
}
int main(){
    cin>>T;
    while(T--){
        cin>>x>>a.x>>a.v>>b.x>>b.v;
        if(a.x>b.x) swap(a,b);
        dou ans=(x+min(a.x,x-a.x))/a.v;
        ans=min(ans,(x+min(b.x,x-b.x))/b.v);
        ans=min(ans,max(b.x/b.v,(x-a.x)/a.v));
        printf("%.6lf\n",min(ans,solve()));
    }
    return 0;
}