← 返回题目列表

Codeforces · 2228/D

D. 早苗、克罗斯和彩色

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

信仰是为转瞬即逝的人们而存在
— 信仰之山

山上,早苗凝视着星空。信仰,对于她来说,是风雨交汇、选择分歧的地方,也是四方交汇的地方。为了圣十字的荣耀,让我们一起追寻信仰的标志。

平面上有 $$$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 \gt k_2$$$):该点为红色。
  • 右上角($$$x \gt k_1$$$ 和 $$$y \gt k_2$$$):该点呈绿色。
  • 左下角($$$x\leq k_1$$$ 和 $$$y\leq k_2$$$):该点为蓝色。
  • 右下角($$$x \gt k_1$$$ 和 $$$y\leq k_2$$$):该点为黄色。
第三个测试用例的有效着色,其中 $$$k_1=4$$$ 和 $$$k_2=5$$$。

找出不同颜色的数量,其中当且仅当存在至少一个颜色不同的点时,两种颜色才被认为是不同的, 无论选择 $$$k_1$$$ 和 $$$k_2$$$。

输入

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

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

下面的 $$$n$$$ 行每行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$),代表第 $$$i$$$ 个点的坐标。

保证每个测试用例中的点都是成对不同的。

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

输出

对于每个测试用例,输出不同颜色的数量。

示例

输入
复制

5
4
1 1
2 2
3 3
4 4
4
1 4
4 1
1 1
4 4
8
7 2
5 7
2 7
1 3
6 7
3 6
7 5
1 6
8
6 1
3 6
1 4
1 1
4 2
5 5
3 4
4 1
6
5 5
5 4
3 5
1 5
5 3
2 2

输出
复制

0
1
12
8
4

注意

在第一个测试用例中,不存在有效的交叉。

在第二个测试用例中,选择 $$$x = y = 2$$$ 会产生有效的着色。可以证明这种颜色是独一无二的。

在第三个测试用例中,图例中显示了有效的颜色。