Problem Description

Given two line segments on a 2D Cartesian plane, you need to randomly choose one point from each segment with equal probability, and compute the expected value of the Euclidean distance between the two points.

Input Format

There are multiple groups of testdata. The first line contains an integer $T$ ($1 \leq T \leq 10^5$), indicating the number of test cases. For each test case:

The first line contains four integers $x_1$, $y_1$, $x_2$, and $y_2$ ($-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$), meaning that the two endpoints of the first segment are $(x_1, y_1)$ and $(x_2, y_2)$.

The second line contains four integers $x_3$, $y_3$, $x_4$, and $y_4$ ($-10^3 \le x_3, y_3, x_4, y_4 \le 10^3$), meaning that the two endpoints of the second segment are $(x_3, y_3)$ and $(x_4, y_4)$.

It is guaranteed that both segments have positive length.

Output Format

For each test case, output one number per line, representing the expected distance between the two randomly chosen points.

Your answer will be accepted if the relative error or absolute error does not exceed $10^{-9}$. Specifically, let your answer be $a$ and the judge’s answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$.

3
0 0 1 0
0 0 1 0
0 0 1 0
0 0 0 1
0 0 1 0
0 1 1 1

0.333333333333333333
0.765195716464212691
1.076635732895178009

Hint

Thanks to “computational intelligence”, we know that:

For the first sample, the expected distance is

$$\int_{0}^{1} \int_{0}^{1} |x_0 - x_1| \,\mathrm{d}x_0 \,\mathrm{d}x_1 = \frac{1}{3} \approx 0.333333333333333333;$$

For the second sample, the expected distance is

$$\int_{0}^{1} \int_{0}^{1} \sqrt{x^2+y^2} \,\mathrm{d}x \,\mathrm{d}y = \frac{\sqrt{2}+\ln(1+\sqrt{2})}{3} \approx 0.765195716464212691;$$

For the third sample, the expected distance is

$$\int_{0}^{1} \int_{0}^{1} \sqrt{(x_0-x_1)^2+1} \,\mathrm{d}x_0 \,\mathrm{d}x_1 = \frac{2-\sqrt{2}+3\ln(1+\sqrt{2})}{3} \approx 1.076635732895178009.$$

Translated by ChatGPT 5