← 返回题目列表

Codeforces · 1470/F

F. 奇怪的覆盖物

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

在飞机上您将获得 $$$n$$$ 积分。

请求两个轴对齐矩形的面积之和最小,使得每个点至少包含在其中一个矩形中。

请注意,所选矩形可能是退化的。矩形包含位于其内部或边界上的所有点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。

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

以下 $$$n$$$ 行包含点 $$$x_i$$$ 和 $$$y_i$$$ 的坐标 ($$$0 \le x_i, y_i \le 10^9$$$)。保证点是不同的。

保证所有测试用例的值 $$$n$$$ 之和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,打印一个整数——面积的最小总和。

示例

输入 #1

3
2
9 1
1 6
2
8 10
0 7
4
0 0
1 1
9 9
10 10

输出 #1

0
0
2

注意

在前两个测试用例中,答案由 2 个退化矩形组成。在第三个测试用例中,可能的答案之一由两个矩形 $$$1 \times 1$$$ 组成,左下角为 $$$(0,0)$$$ 和 $$$(9,9)$$$。