← 返回题目列表

Codeforces · 1468/F

F. 全转

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

飞机上有 $$$n$$$ 人。第 $$$i$$$ 人位于点 $$$(x_i, y_i)$$$,并且最初查看点 $$$(u_i, v_i)$$$。

同一时刻,所有人都会开始以相同的角速度同步顺时针旋转。它们将旋转直至完成 $$$360$$$ 度的完整旋转。

据说,如果$$$A$$$ 看着$$$B$$$ 的方向,而$$$B$$$ 看着$$$A$$$ 的方向,则$$$A$$$ 和$$$B$$$ 会进行目光接触。如果 $$$C$$$ 位于 $$$A$$$ 和 $$$B$$$ 之间,则不会妨碍 $$$A$$$ 和 $$$B$$$ 进行目光接触。一个人可以同时与多个人进行目光接触。

计算在旋转过程中(包括初始时刻)至少进行一次目光接触的人数对。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 人数。以下 $$$n$$$ 行描述人物,每行包含四个空格分隔的整数 $$$x_i, y_i, u_i, v_i$$$ ($$$|x_i|, |y_i|, |u_i|, |v_i| \le 10^9$$$; $$$x_i \ne u_i$$$ 或 $$$y_i \ne v_i$$$),其中($$$x_i, y_i$$$) 是第 $$$i$$$ 人所在点的坐标,($$$u_i$$$, $$$v_i$$$) 是第 $$$i$$$ 人最初看到的点的坐标。每个测试用例中每个人的位置都是唯一的。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 在旋转期间(包括初始时刻)至少进行一次目光接触的人数对。

示例

输入 #1

3
2
0 0 0 1
1 0 2 0
3
0 0 1 1
1 1 0 0
1 0 2 0
6
0 0 0 1
1 0 1 2
2 0 2 3
3 0 3 -5
4 0 4 -5
5 0 5 -5

输出 #1

0
1
9