CF2141G.Good Robot Paths

在笛卡尔平面上，有 $n$ 个位置被涂成黑色，其余所有点均为白色。每个黑色点的坐标都是整数。

此外，还有一个机器人，每次可以向 ‘U’（上）、‘D’（下）、‘L’（左）、‘R’（右）四个方向中的任意一个移动一个单位。

机器人从点 $p_1$ 到点 $p_2$ 的一条路径，是一串指令序列，使得机器人初始位于 $p_1$，执行该序列后最终到达 $p_2$。

从 $p_1$ 到 $p_2$ 的最短路径，是指令数量尽可能少的路径。

你需要统计有多少对点 $p_i$、$p_j$（$i \ne 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}$。

对于每组测试用例，输出一个整数，表示满足条件的点对数量。

在第一个测试用例中，有 $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$

由 ChatGPT 5 翻译