Sam住在Awesomeburg,其市中心呈三角形。另外,关于三角形,下列说法正确的是:
- 它的顶点有整数坐标,
- 顶点坐标非负,并且
- 它的顶点不在一条线上。
如果他可以从线 $$$y = 0$$$ 上的至少一个点沿着某条直线行走而不穿过三角形的内部到达该点,则他称市中心边界(即三角形的边界)上的一点是安全的。
图中市中心用灰色标记。第一条路径无效,因为它不是沿着直线走的。第二条路径无效,因为它与市中心内部相交。第三条和第四条路径是正确的。
求市中心边界不安全部分的总长度。可以证明,这些部分都是段,且数量是有限的。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例包含三行,每行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) – 市中心边界顶点的坐标。
输出
对于每个测试用例,打印一个数字 - 问题的答案。
如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。正式让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$,您的答案将被视为正确。
示例
输入 #1
5 8 10 10 4 6 2 4 6 0 1 4 2 14 1 11 2 13 2 0 0 4 0 2 4 0 1 1 1 0 0
输出 #1
0.0000000 0 2.0000 0.00 1
注意
图中显示了前三个测试用例的市中心。三角形根据它们所属的测试用例的索引进行枚举。
在前两个测试用例中,市中心边界上的所有点都是安全的,因此答案是 $$$0$$$。
下图中第三个测试用例的不安全点用黑色标记:
在第四个测试用例中,市中心边界上的所有点都是安全的。