#GYM104639J. Minimum Manhattan Distance
Minimum Manhattan Distance
Description
Recall that on a two-dimensional plane, the Manhattan distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|$. If both coordinates of a point are all integers, then we call this point an integer point.
Given two circles $C_1,C_2$ on the two-dimensional plane, and guaranteed the $x$-coordinates of any point in $C_1$ and any point in $C_2$ are different, and the $y$-coordinates of any point in $C_1$ and any point in $C_2$ are different.
Each circle is described by two integer points, and the segment connecting the two points represents a diameter of the circle.
Now you need to pick a point $(x_0,y_0)$ inside or on the $C_2$ such that minimize the expected value of the Manhattan distance from $(x_0,y_0)$ to a point inside $C_1$ , if we choose this point with uniformly probability among all the points with a real number coordinate inside $C_1$.
The first line contains a single integer $t\ (1\le t\le 10^5)$ , representing the number of test cases.
Then follow the descriptions of each test case.
The first line contains $4$ integers $x_{1,1},y_{1,1},x_{1,2},y_{1,2}$, representing the segment connecting $(x_{1,1},y_{1,1})$ and $(x_{1,2},y_{1,2})$ is a diameter of the circle $C_1$.
The second line contains $4$ integers $x_{2,1},y_{2,1},x_{2,2},y_{2,2}$, representing the segment connecting $(x_{2,1},y_{2,1})$ and $(x_{2,2},y_{2,2})$ is a diameter of the circle $C_2$.
All the coordinates input are integers in the range $[-10^5, 10^5]$ .
For each test case, output a single line with a real number - the minimum expected Manhattan distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. That is, if your answer is $a$, and the jury's answer is $b$, then the solution will be accepted if $\frac{|a-b|}{\max (1,|b|)} \leq 10^{-6}$ .
Input
The first line contains a single integer $t\ (1\le t\le 10^5)$ , representing the number of test cases.
Then follow the descriptions of each test case.
The first line contains $4$ integers $x_{1,1},y_{1,1},x_{1,2},y_{1,2}$, representing the segment connecting $(x_{1,1},y_{1,1})$ and $(x_{1,2},y_{1,2})$ is a diameter of the circle $C_1$.
The second line contains $4$ integers $x_{2,1},y_{2,1},x_{2,2},y_{2,2}$, representing the segment connecting $(x_{2,1},y_{2,1})$ and $(x_{2,2},y_{2,2})$ is a diameter of the circle $C_2$.
All the coordinates input are integers in the range $[-10^5, 10^5]$ .
Output
For each test case, output a single line with a real number - the minimum expected Manhattan distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. That is, if your answer is $a$, and the jury's answer is $b$, then the solution will be accepted if $\frac{|a-b|}{\max (1,|b|)} \leq 10^{-6}$ .
1
0 0 2 1
4 5 5 2
4.2639320225