목초지 나누기

면접 대비

시간 제한2초메모리 제한512 MB

요약

모든 점을 하나의 직사각형 대신 서로 겹치지 않는 축에 평행한 두 직사각형으로 감쌀 때 절약되는 면적을 구합니다.

난이도: 보통10점 중 6점
유형: 정렬, 누적 합, 기하
정답자: 아직 제출이 없습니다

문제

농부 존의 목장에 소 $N$ 마리가 평면 위 서로 다른 위치에 서 있다. 존은 소를 모두 둘러싸는 직사각형 울타리를 하나 세우려 한다. 울타리의 각 변은 $x$ 축이나 $y$ 축에 평행하고, 소를 모두 포함하는 직사각형 중 넓이가 가장 작다. 경계 위에 서 있는 소도 울타리 안에 있는 것으로 친다.

지난 분기에 우유 생산량이 줄어 예산이 빠듯하다. 존은 관리비를 아끼려고 울타리를 하나가 아니라 두 개로 나눠 세워 전체 넓이를 줄이려 한다. 두 울타리도 각 변이 $x$ 축이나 $y$ 축에 평행한 직사각형이고, 둘을 합쳐 소를 모두 포함해야 하며, 경계선끼리도 겹칠 수 없다. 넓이가 0인 울타리도 세울 수 있다. 즉 너비나 높이가 0이어도 된다.

울타리를 하나만 세울 때의 넓이에서 두 울타리의 넓이 합이 가장 작을 때의 값을 뺀 값을 구하라.

입력

첫 줄에 소의 수 $N$ 이 주어진다. ( $3 \le N \le 50000$ )

다음 $N$ 개 줄에 소 한 마리의 좌표 $x$ 와 $y$ 가 공백으로 구분되어 주어진다. ( $1 \le x, y \le 10^9$ )

소의 위치는 모두 다르다.

출력

울타리를 두 개로 나눠 세워 줄일 수 있는 넓이를 정수 하나로 출력한다.

예제7

예제 1
입력
```
6
4 2
8 10
1 1
9 12
14 7
2 3
```
예상 출력
```
107
```
예제 2
입력
```
3
5 1
5 2
5 1000000000
```
예상 출력
```
0
```

예제 3

입력

3
1 1
1000000000 1
1 1000000000

예상 출력

999999998000000001

예제 4
입력
```
4
3 7
9 7
1 7
1000000000 7
```
예상 출력
```
0
```

예제 5

입력

6
1 1
2 2
3 1
1000000000 999999999
999999998 1000000000
999999999 999999998

예상 출력

999999997999999995

예제 6
입력
```
5
5 2
5 8
1 5
9 5
5 5
```
예상 출력
```
24
```
예제 7
입력
```
3
1 2
2 1
3 3
```
예상 출력
```
3
```