题目描述

有 $N$ 个袋子，每个袋子里都有 $2$ 个白色球。第 $i$ 个袋子里的两个球分别写有整数 $x_i$ 和 $y_i$。

你可以为每个袋子的两个球分别涂成红色和蓝色（每个球必须涂一种颜色，且同一个袋子一个红、一个蓝）。

然后，将所有 $2N$ 个球按照颜色分组。

设：

• 红色球上的整数的最大值为 $R_{max}$，
• 红色球上的整数的最小值为 $R_{min}$，
• 蓝色球上的整数的最大值为 $B_{max}$，
• 蓝色球上的整数的最小值为 $B_{min}$。

请你最小化 $(R_{max} - R_{min}) \times (B_{max} - B_{min})$ 的值。

输入格式

输入由标准输入给出，格式如下：

$N$ $x_1$ $y_1$ $x_2$ $y_2$ … $x_N$ $y_N$

输出格式

输出问题的最小值。

样例 1

输入

3
1 2
3 4
5 6

输出

15

样例 2

输入

3
1010 10
1000 1
20 1020

输出

380

样例 3

输入

2
1 1
1000000000 1000000000

输出

999999998000000001

说明/提示

限制

• $1 \leq N \leq 200\,000$
• $1 \leq x_i, y_i \leq 10^9$

样例说明 1

将写有 $x_1$、$x_2$、$y_3$ 的球涂成红色，将写有 $y_1$、$y_2$、$x_3$ 的球涂成蓝色，可以得到最优解。

由 ChatGPT 5 翻译