Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3928
Rectangle and Rectangle

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Assuming that two points are chosen randomly (with uniform distribution) within a rectangle, it is possible to determine the expected value of the distance between these two points.

It can be verified that, within a rectangle of sides a and b, the expected value of the distance between two random points is

\frac{1}{15}\left[\frac{a^3}{b^2}+\frac{b^3}{a^2}+\sqrt{a^2+b^2}\left(3-\frac{a^2}{b^2}-\frac{b^2}{a^2}\right)+\frac{5}{2}\left(\frac{b^2}{a}\log{\frac{a+\sqrt{a^2+b^2}}{b}}+\frac{a^2}{b}\log{\frac{b+\sqrt{a^2+b^2}}{a}}\right)\right]

Now, point A is chosen randomly (with uniform distribution) within rectangle P, while point B is chosen randomly within rectangle Q similarly. Both sides of rectangle P and Q are parallel to the axes. Your task is to find the expected value of the distance between A and B.

choose 2 random points in two rectangles

Input

There are multiple test cases. The first line of input is an integer T ≤104 indicates the number of test cases. For each test case:

There are 8 integers x1, x2, y1, y2, x3, x4, y3 and y4. Rectangle P is {(x, y) | x1xx2, y1yy2} and rectangle Q is {(x, y) | x3xx4, y3yy4}. (0≤ x1< x2≤ 100, 0≤ y1< y2≤ 100, 0≤ x3< x4≤ 100, 0≤ y3< y4≤ 100)

Output

For each test case, output the expected value of the distance between A and B. Absolute error or relative error less than 10-8 will be accepted.

Sample Input

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

Sample Output

0.52140543316472
5.67158783860584

Author: ZHOU, Yuchen
Source: The 16th Zhejiang University Programming Contest
Submit    Status