P16317 [ICPC 2023 Jinan R] Computational Intelligence

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.

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.

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

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