27709번 - 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 = (A_x, A_y) to corner B = (B_x, B_y), the shortest way has length |A_x − B_x| + |A_y − B_y|. 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.

Given the two corners A = (A_x, A_y),B = (B_x, B_y) 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.

입력

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 A_x, A_y, B_x, B_y specifying the points A = (A_x, A_y) and B = (B_x, B_y), and three rational numbers P, Q, R specifying the Broadway as explained above.

출력

For 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⁻⁹.

제한

Easy (1점)

• -1 000 ≤ A_x, A_y, B_x, B_y ≤ 1 000
• -200 ≤ P ≤ 200
• Q = 1
• -20 000 ≤ R ≤ 20 000

Hard (2점)

• -1 000 000 ≤ A_x, A_y, B_x, B_y ≤ 1 000 000
• -25 ≤ P ≤ 25
• Q = 1
• -2 000 000 ≤ R ≤ 2 000 000

힌트