유적 보존 분담

유적 보존 단체 ICPC(International Community for Preservation of Constructions)와 JAG(Japanese Archaeologist Group)가 있다. 최근 어떤 지역에서 유적이 많이 발견되었고, 두 단체는 유적을 나누어 ICPC가 일부를, JAG가 나머지를 보존하기로 했다.

나누는 규칙은 다음과 같다.

1. 남북 방향의 세로 직선을 하나 긋는다. 이 직선은 어떤 유적도 지나지 않아야 한다.
2. 직선의 서쪽에 있는 유적은 ICPC가, 동쪽에 있는 유적은 JAG가 보존한다. 직선의 한쪽에 유적이 하나도 없어도 되며, 이 경우 그 단체는 보존할 유적이 없다.

문제는 직선을 어디에 그을지이다. 각 단체는 배정받은 유적 전체를 감싸는 울타리를 정확히 하나 세워 보존하며, 예산을 아끼기 위해 울타리의 길이를 최소로 만든다. 울타리가 감싸는 영역이 넓으면 안쪽을 관리하는 데 비용이 많이 들기 때문에, 두 단체는 보존 비용의 합, 즉 두 울타리가 감싸는 영역의 넓이의 합을 최소로 만들고 싶다.

직선을 알맞게 그었을 때 두 울타리가 감싸는 영역의 넓이의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 하나로 이루어진다.

N
x1 y1
...
xN yN

첫째 줄에 발견된 유적의 수 $N$ ($1 \le N \le 100{,}000$)이 주어진다. 다음 $N$개의 줄에는 유적의 위치가 주어진다. 그중 $i$번째 줄에는 정수 $x_i$와 $y_i$가 주어지며, $i$번째 유적이 지역의 기준점에서 동쪽으로 $x_i$, 북쪽으로 $y_i$만큼 떨어진 곳에 있다는 뜻이다. 유적에 대해 다음을 가정해도 된다.

• $-10^9 \le x_i, y_i \le 10^9$
• 유적의 크기는 무시한다. 즉, 유적을 점으로 생각해도 된다.
• 같은 위치에 있는 유적은 없다.

직선을 알맞게 그었을 때의 보존 비용의 합, 즉 두 울타리가 감싸는 영역의 넓이의 합의 최솟값을 출력한다. 넓이의 합은 항상 정수이거나 정수에 $0.5$를 더한 값이며, 가장 가까운 정수로 반올림해서 출력한다. 소수 부분이 정확히 $0.5$이면 올림한다.