27529번 - 양 가두기

무한한 격자 모양의 농장에 $N$마리의 양이 살고 있다. 양 한 마리는 격자의 한 칸인 $1\times1$ 정사각형을 차지하며, 상하좌우로 인접한 칸을 따라 움직일 수 있다.

양치기 소년 아멜은 우리를 만들기 위하여 양이 움직이지 못하도록 고정한 뒤 모든 양의 위치를 기록하였다. $i$번째 양의 위치는 아멜이 서 있는 칸과 $x$축의 양의 방향으로 떨어진 거리 $x_i$와 $y$축의 양의 방향으로 떨어진 거리 $y_i$ 두 개의 정수로 나타낸다. 양의 위치에 따라 $x_i, y_i \le 0$일 수 있으며 양과 아멜은 같은 칸에 위치할 수 있다.

아멜은 길이가 $1$인 울타리 여러 개를 사용하여 양을 모두 가둘 수 있는 우리를 만들려고 한다. 울타리는 두 끝점이 모두 격자점과 일치하도록 놓아야 한다. 양은 울타리를 넘어 이동할 수 없다.

우리를 완성한 뒤 고정했던 양들을 이동할 수 있도록 다시 풀어줄 것이다. 이때 양이 우리 밖으로 달아날 수 없어야 하며, 모든 양과 서로 만날 수 있어야 한다. 더 구체적으로, 모든 양에 대해 이동할 수 있는 칸이 유한하여야 하며 다른 모든 양의 위치까지 전부 이동할 수 있어야 한다.

그림 1. 잘못된 우리: 양이 달아날 수 있다.	그림 2. 잘못된 우리: 양이 서로 만날 수 없다.
그림 3. 조건에 맞는 우리

울타리는 무겁기 때문에 최대한 적게 사용하여 우리를 만들려고 한다. 또한, 우리를 관리하기 편하도록 넓이를 최대한 작게 만들려고 한다.

아멜에게 필요한 울타리의 최소 개수와, 울타리를 최소 개수만큼 사용할 때 우리의 최소 넓이를 구하여라.

첫째 줄에 양의 마릿수 $N$이 주어진다. ($1 \le N \le 100\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 한 줄에 한 마리씩 양의 위치를 나타내는 두 정수 $x_i, y_i$가 공백을 사이에 두고 주어진다. ($-10^9 \le x_i, y_i \le 10^9$)

입력으로 주어지는 모든 위치는 서로 다르다.

아멜에게 필요한 울타리의 최소 개수와 그때 우리의 최소 넓이를 공백을 사이에 두고 출력한다.