← 返回题目列表

Codeforces · 2141/G

G. 良好的机器人路径

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

在笛卡尔平面上,有 $$$n$$$ 不同的点涂成黑色,而所有其他点都涂成白色。每个黑点都有整数坐标。

还有一种机器人可以向任何方向移动一个单元'U'(向上),'D'(向下),'L'(左),或 'R'(右)使用单个命令。

机器人从点 $$$p_{1}$$$ 到点 $$$p_{2}$$$ 的路径是一系列命令,如果机器人从点 $$$p_{1}$$$ 开始执行此序列,它将到达点 $$$p_{2}$$$。

机器人从点 $$$p_{1}$$$ 到点 $$$p_{2}$$$ 的最短路径是一条路径,其序列由尽可能少的命令组成。

您需要计算点对 $$$p_i$$$, $$$p_j$$$ ($$$i \neq j$$$) 的数量,使得对于这对点,满足以下条件:

全部 具有整数坐标的点 任何 机器人从点$$$p_{i}$$$到点$$$p_{j}$$$的最短路径被漆成黑色。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — 涂成黑色的点数。

每个测试用例接下来的 $$$n$$$ 行包含两个整数 $$$x_{i}, y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$) - 点 $$$p_{i}$$$ 的坐标。所有点都是成对不同的。

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

输出

对于每个测试用例,输出一个整数 - 问题的答案。

示例

输入
复制

3
5
0 0
1 0
0 1
1 1
2 0
18
0 0
-1 0
-2 0
0 -1
-1 -1
0 1
1 1
0 2
1 2
2 2
1 3
6 -2
5 -2
5 -3
6 -3
4 -3
3 -3
5 -4
3
-100 100
-101 99
-99 101

输出
复制

16
70
0

注意

在第一个测试用例中,有 $$$16$$$ 合适的点对:

  • $$$p_{1}, p_{2}$$$
  • $$$p_{1}, p_{3}$$$
  • $$$p_{1}, p_{4}$$$
  • $$$p_{1}, p_{5}$$$
  • $$$p_{2}, p_{1}$$$
  • $$$p_{2}, p_{3}$$$
  • $$$p_{2}, p_{4}$$$
  • $$$p_{2}, p_{5}$$$
  • $$$p_{3}, p_{1}$$$
  • $$$p_{3}, p_{2}$$$
  • $$$p_{3}, p_{4}$$$
  • $$$p_{4}, p_{1}$$$
  • $$$p_{4}, p_{2}$$$
  • $$$p_{4}, p_{3}$$$
  • $$$p_{5}, p_{1}$$$
  • $$$p_{5}, p_{2}$$$