#P18387. Emergency Pipeline Repair
Emergency Pipeline Repair
Emergency Pipeline Repair
城市需要检修 条管线。平面上,每条管线是一条无限延伸的直线,用经过它的两个不同的整数坐标点表示。
检修设备展开后是一条线段。只要线段与一条管线存在公共点,就能检修这条管线;在线段的端点接触也算相交。
求能够同时与全部 条直线相交的线段的最短长度。线段的端点可以是任意实数坐标,不受输入点的坐标范围限制。输入的直线可以平行、重合或共点。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例首先给出整数 ,随后给出 行,每行四个整数 ,表示经过 和 的直线。
约束如下:
- ;
- ;
- ;
- 全部测试用例的 之和不超过 。
输出格式
对每个测试用例输出一行实数,表示所求最短长度。
设你的输出为 ,裁判答案为 ,当且仅当
时,该答案被接受。注意相对误差的基准是裁判答案 。
样例输入 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
样例说明
第一组可取三角形顶点到对边所在直线的垂线段,最优长度是 。第二组可以取单位正方形的一条对角线,长度为 。第三组只有一条管线,长度为 的退化线段即可。
