#P9643. Grid City Rescue
Grid City Rescue
Grid City Rescue
In Grid City, the roads lie along the lines \(x=k\) and \(y=k\) for every integer \(k\). BaoBao lives at \(A=(x_A,y_A)\) and wants to go to the shopping mall at \(C=(x_C,y_C)\). However, he walks at a speed of \(a\) units per minute, which might be too slow. His friend DreamGrid, who drives at speed \(b\) units per minute and lives at \(B=(x_B,y_B)\), sets off at the same time in order to help. When they meet, DreamGrid picks up BaoBao instantly (without any delay) and they continue together at speed \(b\) along the grid.
The movement is restricted to the grid (i.e. only along the horizontal and vertical roads), so the distance between two points \(P=(x_1,y_1)\) and \(Q=(x_2,y_2)\) is given by the Manhattan distance:
[ d(P,Q)=|x_1-x_2|+|y_1-y_2| ]
BaoBao can choose to either go directly on foot or be picked up by DreamGrid if it reduces the total travel time. If they meet at some grid intersection \(M=(X,Y)\), then BaoBao will have walked for \(\frac{d(A,M)}{a}\) minutes and DreamGrid will have driven for \(\frac{d(B,M)}{b}\) minutes. They meet at time
[ T_{\text{meet}} = \max\left(\frac{d(A,M)}{a}, \frac{d(B,M)}{b}\right), ]
and the remaining journey from \(M\) to \(C\) takes \(\frac{d(M,C)}{b}\) minutes. The overall time when using a pick-up at \(M\) is
[ T(M)=\max\left(\frac{d(A,M)}{a}, \frac{d(B,M)}{b}\right)+\frac{d(M,C)}{b}. ]
Your task is to compute the minimum possible time needed for BaoBao to reach the shopping mall, considering both direct walking as well as any meeting strategy.
inputFormat
The input consists of one line containing eight space-separated integers:
- \(x_A\) \(y_A\): Coordinates of BaoBao's home.
- \(x_B\) \(y_B\): Coordinates of DreamGrid's home.
- \(x_C\) \(y_C\): Coordinates of the shopping mall.
- \(a\): BaoBao's walking speed.
- \(b\): DreamGrid's driving speed.
All coordinates are integers and speeds are positive integers.
outputFormat
Output a single number, the minimum time (in minutes) needed for BaoBao to reach the shopping mall. An answer with an absolute or relative error of at most 10^{-6} is considered correct.
sample
0 0 0 0 10 0 1 10
1.0
</p>