The Great Blue Heron
is a remarkable bird which lives around wetlands and coastlines.
During migration season they can travel up to
hundreds of miles (or kilometers) in a single day, and able to achieve distances
up to 60 miles (100 kilometers) in a single sustained flight.
Let's imagine a perfectly straight coastline with two islands A and B
located somewhere off the coast. There is a heron located at island A who
plans to travel to island B, stopping once at the coastline at some point
M. However the heron doesn't wish to expend energy unnecessarily and so
will choose the point M which minimizes the total travel distance required.
A possible path of a Heron traveling from island A to island B, stopping
on the coast at point M along the way.
Problem Statement
The coastline in this problem will run along the y-axis, with all negative
x values representing land and all positive x values representing ocean.
You will be given two sets of (x, y) coordinates corresponding to two islands
(assume the heron will begin and end its journey from these exact coordinates).
You must return a single value M_Y, corresponding to the point on the
y-axis with coordinates (0, M_Y) which minimizes the heron's total travel
distance.
Note that even if the total journey would be shorter by directly traveling
between points A and B without first stopping at the coast, the heron's
journey still must stop at the coast at a single point.
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each containing four space-separated values in the
format x1 y1 x2 y2 corresponding to the (x, y) coordinates of two islands.
Answer
Should consist of Q space-separated values, corresponding to the value of
M_Y for each testcase.
Error should be less than 1e-6
Example
input data:
1
1.234 -5.678 9.876 5.432
answer:
-4.444000