← 返回题目列表

AtCoder · arc073_c

E. 球着色

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

分数: 700 点

问题陈述

有 N 袋子,每个袋子里有两个白球。 i-第一个盒子包含两个带有整数的球 上面分别写着 x_i 和 y_i 。

对于每个袋子,您将其中一个球涂成红色,将另一个球涂成蓝色。

随后, 2N 球将根据颜色进行分类。

然后,我们将定义以下内容:

  • R_{max}:写在红色球上的最大整数
  • R_{min}:写在红色球上的最小整数
  • B_{max}:写在蓝色球上的最大整数
  • B_{min}:写在蓝色球上的最小整数

找到最小可能值 (R_{max} - R_{min}) \times (B_{max} - B_{min}).

约束

  • 1 ≤ N ≤ 200,000
  • 1 ≤ x_i, y_i ≤ 10^9

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_N y_N

输出

打印最小可能值。


示例输入 1

3
1 2
3 4
5 6

示例输出 1

15

最佳解决方案是将球涂成 x_1, x_2, y_3 红色,并将球涂成 y_1, y_2, x_3 蓝色。


示例输入 2

3
1010 10
1000 1
20 1020

示例输出 2

380

示例输入 3

2
1 1
1000000000 1000000000

示例输出 3

999999998000000001