← 返回题目列表

Codeforces · 1850/G

G. 晨星

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

指南针直接指向晨星。它只能指向八个方向之一:四个基本方向(N、S、E、W)或某种组合(NW、NE、SW、SE)。否则,它会破裂。

指南针可以指向的方向。

平面上有 $$$n$$$ 具有整数坐标的不同点。有多少种方法可以将指南针放在一个地方,而将晨星放在另一个地方,以使指南针不会损坏?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 点数。

接下来是 $$$n$$$ 行,每行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — 每个点的坐标,所有点都有不同的坐标。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 不破坏罗盘的点对的数量。

示例

输入 #1

5
3
0 0
-1 -1
1 1
4
4 5
5 7
6 9
10 13
3
-1000000000 1000000000
0 0
1000000000 -1000000000
5
0 0
2 2
-1 5
-1 10
2 11
3
0 0
-1 2
1 -2

输出 #1

6
2
6
8
0

注意

在第一个测试用例中,任何一对点都不会破坏指南针:

- 指南针位于 $$$(0,0)$$$,晨星位于 $$$(-1,-1)$$$:指南针将指向 $$$\text{SW}$$$。
- 指南针位于 $$$(0,0)$$$,晨星位于 $$$(1,1)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(-1,-1)$$$,晨星位于 $$$(0,0)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(-1,-1)$$$,晨星位于 $$$(1,1)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(1,1)$$$,晨星位于 $$$(0,0)$$$:指南针将指向 $$$\text{SW}$$$。
- 指南针位于 $$$(1,1)$$$,晨星位于 $$$(-1,-1)$$$:指南针将指向 $$$\text{SW}$$$。

在第二个测试用例中,只有两对点不会破坏指南针:

- 指南针位于 $$$(6,9)$$$,晨星位于 $$$(10,13)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(10,13)$$$,晨星位于 $$$(6,9)$$$:指南针将指向 $$$\text{SW}$$$。