分数: 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