406387: GYM102394 D Driverless Car

A driverless car company has a rectangular experiment field on a 2D Cartesian plane. Its four sides are all parallel to the coordinate axes. The bottom-left corner of the field is at coordinate $$$(x_l,y_l)$$$ while the top-right corner is at coordinate $$$(x_r,y_r)$$$.

There are two segments $$$A$$$ and $$$B$$$ lying strictly inside the rectangle. $$$A$$$ and $$$B$$$ share no common points. There is also a car on the plane, which can be regarded as a point. It will start at point $$$S$$$ on the border of the rectangle, move to somewhere strictly inside the rectangle, and finally stop at another point $$$T$$$ on the border of the rectangle. The experiment requires that the distance between the car and the segment $$$A$$$ must be equal to the distance between the car and the segment $$$B$$$ at all times during the movement (including when the car is at $$$S$$$ and $$$T$$$). Also, $$$S$$$ and $$$T$$$ must be two different points. The distance between a point $$$P$$$ and a segment $$$Q$$$ is the minimum Euclidean distance from $$$P$$$ to any point on $$$Q$$$.

The figure above corresponds to the sample test

Please write a program to help the company find a valid path of movement of the car, such that the length of the path is minimized, or determine that no valid paths exist.

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \leq T \leq 10^5$$$), the number of cases.

For each case, the first line of the input contains four integers $$$x_l,y_l,x_r,y_r\ (-1\,000 \le x_l < x_r \le 1\,000,$$$ $$$-1\,000 \le y_l < y_r \le 1\,000)$$$, denoting the coordinates of the bottom-left and the top-right corners of the rectangle. Each of the next two lines contains four integers $$$x_1,y_1,x_2,y_2$$$, denoting a segment that connects $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, where $$$x_1,x_2\in [x_l+1,x_r-1]$$$ and $$$y_1,y_2\in [y_l+1,y_r-1]$$$.

For each case, it is guaranteed that the two endpoints of each segment do not coincide, and these two segments share no common points.

For each case, if a valid path exists, print a single line containing a single real number, the minimum length of the path. Otherwise, print a single number $$$0$$$ instead. Your answer will be considered correct if the absolute or relative error does not exceed $$$10^{-9}$$$.

Formally, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer will be considered correct if and only if $$$\frac{|a - b|}{\max\{1, |b|\}} \le 10^{-9}$$$.

1
0 0 7 6
2 4 4 4
3 2 5 2

7.552593593868681136