← 返回题目列表

Codeforces · 1486/B

B. 东方展览

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

您和您的朋友住在 $$$n$$$ 的房子里。每栋房子都位于二维平面上的一个具有整数坐标的点上。同一地点可能有不同的房屋。该市市长正在向您询问东部展览馆的建设场地。您必须找到地点的数量(具有整数坐标的点),以便所有房屋到展览的总距离最小。展览可以和一些房子建在同一地点。两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的距离为 $$$|x_1 - x_2| + |y_1 - y_2|$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 1000)$$$。接下来的 $$$n$$$ 行描述了房屋 $$$(x_i, y_i)$$$ $$$(0 \leq x_i, y_i \leq 10^9)$$$ 的位置。

保证所有$$$n$$$的总和不超过$$$1000$$$。

输出

为每个测试用例输出一个整数 - 展览的不同位置的数量。展览可以和一些房子建在同一地点。

示例

输入 #1

6
3
0 0
2 0
1 2
4
1 0
0 2
2 3
3 1
4
0 0
0 1
1 0
1 1
2
0 0
1 1
2
0 0
2 0
2
0 0
0 0

输出 #1

1
4
4
4
3
1

注意

以下是示例测试用例的图像。蓝点代表房屋,绿色代表展览的可能位置。

第一个测试用例。

第二个测试用例。

第三个测试用例。

第四个测试用例。

第五个测试用例。

第六个测试用例。这里两栋房子都位于$$$(0, 0)$$$。