Broadway
The Manhattan in the New York City has really a nice topology. So nice, it is often idealized to a rectangular grid. If you want to go from corner A = (Ax,Ay) to corner B = (Bx,By), the shortest way has length |Ax − Bx| + |Ay − By|. Or so they told you in school.
The truth is, the correct definition of a Manhattan metric has to involve the Broadway – a road that leads across the neatly aligned system of streets and avenues. In this problem we finally correct this horrible mistake made by the mathematical community.
Problem specification
Given the two corners A = (Ax,Ay),B = (Bx,By) and three rational numbers P, Q, R that describe the Broadway, your task is to find the length of the shortest path between points A and B.
The road network consists of the following roads:
* For each integer Z, there is an avenue described by the equation x = Z.
* For each integer Z, there is a street described by the equation y = Z.
* The Broadway is described by the equation Px + Qy = R.
When moving from A to B, we can only move along the roads and change roads at intersections.
Input The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of one line containing seven numbers:
four integers Ax,Ay,Bx,By specifying the points A = (Ax,Ay) and B = (Bx,By),
and three rational numbers P,Q,R specifying the Broadway as explained above.
Each test case consists of one line containing seven numbers:
four integers Ax,Ay,Bx,By specifying the points A = (Ax,Ay) and B = (Bx,By),
and three rational numbers P,Q,R specifying the Broadway as explained above.
OutputFor each test case output a single line containing the length of the shortest path from A to B. Output a sufficient number of decimal places. Your output will be judged as correct if it has an absolute or relative error at most 10^-9.
Input:
Output:
2
2 0 -1 1 1.0 1.0 1.0
-2 3 4 -1 1.0 -0.1 0.47Output:
3.414213562373
10Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.