CF2228D Sanae, Cross and Color

信仰属于转瞬即逝之人。 ——《东方风神录》

在山顶上，早苗仰望星空。对她而言，信仰是风与风相遇、道路分岔之处，也是所有方向交汇的地方。为了圣十字的荣光，让我们一起画出信仰的十字吧。 平面上有 $n$ 个互不相同的整点，第 $i$ 个点的坐标为 $(x_i,y_i)$。为了给这些点染色，需要选择两个整数 $k_1$ 和 $k_2$，使得由直线 $x=k_1+0.5$ 与 $y=k_2+0.5$ 划分出的四个区域中，每个区域都至少包含一个点。每个点 $(x,y)$ 根据其所在区域被染成如下颜色： * 左上（$x\leq k_1$ 且 $y>k_2$）：染成**红色**。 * 右上（$x>k_1$ 且 $y>k_2$）：染成**绿色**。 * 左下（$x\leq k_1$ 且 $y\leq k_2$）：染成**蓝色**。 * 右下（$x>k_1$ 且 $y\leq k_2$）：染成**黄色**。  一组合法染色如第三个测试点所示，此时 $k_1=4,\ k_2=5$。 请你求出**不同染色方案**的数量。若两种染色方案中存在至少一个点颜色不同，则认为这两种方案不同；否则，即使它们对应的 $(k_1,k_2)$ 不同，也认为是同一种染色方案。

每个测试文件包含多组数据。 第一行包含一个整数 $t$（$1\le t\le10^4$），表示测试数据组数。 接下来对于每组数据： 第一行包含一个整数 $n$（$4\leq n\leq2\times10^6$）。 接下来 $n$ 行，每行包含两个整数 $x_i,y_i$（$1\leq x_i,y_i\leq n$），表示第 $i$ 个点的坐标。 保证每组数据中的点两两不同，且所有测试数据中 $n$ 的总和不超过 $2\times10^6$。

对于每组数据，输出一个整数，表示不同合法染色方案的数量。

在第一组样例中，不存在合法的十字分割。 在第二组样例中，取 $k_1=k_2=2$ 时可以得到一种合法染色，可以证明这是唯一的一种染色方案。 第三组样例中的图示展示了其中一种合法染色方案。 由 ChatGPT 5 翻译