题目描述

多次给出询问,每次询问给定两条线段,求这两条线段的距离。

两条线段的距离定义为,从两条线段上各取两点,该两点之间的最小距离即为两条线段的距离。


输入格式

第一行一个整数$T$表示询问次数。
接下来$T$行,每行八个整数$x_0,y_0,x_1,y_1,x_2,y_2,x_3,y_3$,表示第一条线段的两个端点为$(x_0,y_0)$和$(x_1,y_1)$,第二条线段的两个端点为$(x_2,y_2)$和$(x_3,y_3)$.


输出格式

输出共$T$行,第$i$表示第$i$次询问的答案,即两条线段的距离保留三位小数。


样例数据

输入

样例1:
3
0 0 1 0 2 1 1 2
1 1 0 1 0 0 1 0
0 1 0 -1 -1 0 1 0 

样例2:
6
0 0 10 0 33 43 62 29
0 0 10 0 0 8 52 56
0 0 10 0 56 19 11 51
0 0 10 0 43 5 8 93
0 0 10 0 30 66 69 32
0 0 10 0 17 47 72 68

输出

样例1:
2.1.414
1.000
0.000

样例2:
48.765
8.000
42.142
32.512
62.892
47.518

备注

$1\leq T \leq 1000$
$0\leq |x|,|y| \leq 10^4$


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解