← 返回题目列表

Codeforces · 1642/A

A. 困难的方式

中文机器翻译题面 查看原题

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$$$。

下图中第三个测试用例的不安全点用黑色标记:

在第四个测试用例中,市中心边界上的所有点都是安全的。