题目描述

给定两条二维笛卡尔平面上的线段，您需要从每条线段上等概率随机选择一个点，并计算两点之间欧氏距离的期望值。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 10^5$）表示测试数据组数，对于每组测试数据：

第一行输入四个整数 $x_1$，$y_1$，$x_2$ 和 $y_2$（$-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$）表示第一条线段的两个端点是 $(x_1, y_1)$ 和 $(x_2, y_2)$。

第二行输入四个整数 $x_3$，$y_3$，$x_4$ 和 $y_4$（$-10^3 \le x_3, y_3, x_4, y_4 \le 10^3$）表示第二条线段的两个端点是 $(x_3, y_3)$ 和 $(x_4, y_4)$。

保证两条线段的长度均为正数。

输出格式

每组数据输出一行一个数，表示两个随机选择的点之间距离的期望值。

如果相对误差或绝对误差不超过 $10^{-9}$，您的答案将被接受。具体来说，设您的答案为 $a$，裁判的答案为 $b$，当且仅当 $\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

提示

感谢“计算智能”，我们可知：

对于第一组样例数据，距离的期望值为

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

对于第二组样例数据，距离的期望值为

$$\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;$$

对于第三组样例数据，距离的期望值为

$$\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.$$