#P18387. Emergency Pipeline Repair

Emergency Pipeline Repair

Emergency Pipeline Repair

城市需要检修 nn 条管线。平面上,每条管线是一条无限延伸的直线,用经过它的两个不同的整数坐标点表示。

检修设备展开后是一条线段。只要线段与一条管线存在公共点,就能检修这条管线;在线段的端点接触也算相交。

求能够同时与全部 nn 条直线相交的线段的最短长度。线段的端点可以是任意实数坐标,不受输入点的坐标范围限制。输入的直线可以平行、重合或共点。

输入格式

第一行一个整数 T≥1T\ge 1,表示测试用例数。

每个测试用例首先给出整数 nn,随后给出 nn 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示经过 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的直线。

约束如下:

  • 1≤n≤1051\le n\le 10^5;
  • −103≤x1,y1,x2,y2≤103-10^3\le x_1,y_1,x_2,y_2\le 10^3;
  • (x1,y1)≠(x2,y2)(x_1,y_1)\ne(x_2,y_2);
  • 全部测试用例的 nn 之和不超过 10510^5。

输出格式

对每个测试用例输出一行实数,表示所求最短长度。

设你的输出为 aa,裁判答案为 bb,当且仅当

∣a−b∣≤10−6max⁡(1,∣b∣)|a-b|\le 10^{-6}\max(1,|b|)

时,该答案被接受。注意相对误差的基准是裁判答案 bb。

样例输入 1

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

样例输出 1

1.788854381948
1.414213562373
0

样例说明

第一组可取三角形顶点到对边所在直线的垂线段,最优长度是 4/54/\sqrt5。第二组可以取单位正方形的一条对角线,长度为 2\sqrt2。第三组只有一条管线,长度为 00 的退化线段即可。

前两组样例的最短相交线段示意图