Migrated from Lutece 3049 最近线段对

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

TAG：扫描线

在欧几里得平面上有$n$个不相交的线段。定义一对线段之间的最短距离是在这两个线段上各取一点，使得这两点间距离尽可能小时的距离。现在你需要找到最近的线段对，并输出其最短距离。

Input

本题包含多组数据。输入的第一行包含一个整数 $T$，表示数据组数。

每组数据第一行包含一个整数 $n$，表示线段数。

接下来的$n$行每行包含四个整数 $x_1,y_1,x_2,y_2$，表示线段的两个端点。

Output

输出一共 $T$ 行，每行包括一个浮点数 $ans_i$ 表示最短距离。

为简化题目，此处的输出遵循以下规则：

1. 若最短距离的实际值小于等于1，则将最终答案设置为1，否则为最短距离的实际值。（设置为1后也要按照科学计数法输出）
2. 将最终答案按照科学计数法输出，保留6位有效数字，格式为 printf("%.5e\n", ans)。

Samples

2
2
0 1 1 2
1 1 2 0
2
-1000000000 -999999999 -999999998 -1000000000
999999998 1000000000 1000000000 999999999

1.00000e+00
2.82843e+09

Constraints

$1≤T≤100$

$2≤n≤100000$，多组数据中所有的 $n$ 和不超过 $100000$

$−10^9≤x_1,y_1,x_2,y_2≤10^9$

Resources

2023 UESTC ICPC Training for Geometry