Closest Pair of Segments

The closest pair of points problem is a well-known problem of computational geometry. In this problem, you are given $n$ points in the Euclidean plane and you need to find a pair of points with the smallest distance between them.

Now, Claris, the brilliant one who has participated in programming contests for several years, is trying to solve a harder problem named the closest pair of segments problem, which also has a quite simple description as above.

However, the problem seems even too hard for Claris and she is asking you for help.

Now $n$ segments are lying on the Euclidean plane, you are asked to pick two different segments and then pick a point on the two segments respectively to minimize the distance between these two points.

For simplicity, any two given segments share no common point, and you don't need to show her the two chosen points, but the distance between them instead.

The input contains several test cases, and the first line contains a single integer $T~(1 \le T \le 200)$, the number of test cases.

For each test case, the first line contains one integer $n~(2 \le n \le 10\,000)$, which is the number of segments on the Euclidean plane.

The following $n$ lines describe all the segments lying on the Euclidean plane, the $i$-th of which contains for integers $x_1, y_1, x_2$ and $y_2$ describing a segment that connects $(x_1,y_1)$ and $(x_2,y_2)$, where $-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$.

It's guaranteed that the two endpoints of each segment do not coincide, any two given segments do not intersect with each other in each test case, and no more than $20$ test cases satisfy $n>1\,000$.

For each test case, output a line containing a single real number for the answer to the closest pair of segments problem with an absolute or relative error of at most $10^{-6}$.

Precisely speaking, assume that your answer is $a$ and and the jury's answer is $b$, your answer will be considered correct if and only if $\frac{|a - b|}{\max\{1, |b|\}} \le 10^{-6}$.

2
2
0 1 1 2
1 1 2 0
2
0 1 1 2
2 2 3 1

0.707106781187
1.000000000000

2019 Multi-University Training Contest 10