200732: [AtCoder]ARC073 E - Ball Coloring

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

There are $N$ bags, each containing two white balls. The $i$-th box contains two balls with integers $x_i$ and $y_i$ written on them, respectively.

For each of these bags, you will paint one of the balls red, and paint the other blue.

Afterwards, the $2N$ balls will be classified according to color.

Then, we will define the following:

  • $R_{max}$: the maximum integer written on a ball painted in red
  • $R_{min}$: the minimum integer written on a ball painted in red
  • $B_{max}$: the maximum integer written on a ball painted in blue
  • $B_{min}$: the minimum integer written on a ball painted in blue

Find the minimum possible value of $(R_{max} - R_{min}) \times (B_{max} - B_{min})$.

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum possible value.


Sample Input 1

3
1 2
3 4
5 6

Sample Output 1

15

The optimal solution is to paint the balls with $x_1$, $x_2$, $y_3$ red, and paint the balls with $y_1$, $y_2$, $x_3$ blue.


Sample Input 2

3
1010 10
1000 1
20 1020

Sample Output 2

380

Sample Input 3

2
1 1
1000000000 1000000000

Sample Output 3

999999998000000001

Input

题意翻译

有$n(1≤n≤200000)$个包,每个包中有两个有编号(编号$<=10^9$)的球,你需要将每个包里的球红蓝染色。 记最大的红球编号为$Rmax$,记最大的蓝球编号为$Bmax$,记最小的红球编号为$Rmin$,记最小的蓝球编号为$Bmin$ 求$(Rmax - Rmin) * (Bmax - Bmin)$的最小值

加入题单

上一题 下一题 算法标签: