다이슨 원

다이슨 구는 태양이나 다른 별의 주위를 감싸서 그 별에서 나오는 에너지 전체를 모으는 이론상의 구조물이다. 공상 과학 작가들은 사회의 에너지 수요가 끝없이 늘어나므로 발전한 문명이 언젠가 이런 구조물을 짓게 될 것이라고 추측해 왔다. 우리가 사는 3차원 공간에서 다이슨 구는 아직 공상의 영역에 머물러 있다. 이웃 차원의 주요 에너지 회사인 Dy & Son은 2차원 세계 Flatland에서 실현 가능성을 검토하는 일을 당신에게 맡겼다.

Dy & Son은 모듈식 다이슨 원을 개발했다. 이 원은 서로 독립된 정사각형 다이슨 유닛들로 이루어져 있으며, 이 유닛들을 이어 붙여 에너지를 모으는 닫힌 고리를 만들 수 있다. 당신의 과제는 Dy & Son이 관심을 가진 별 하나 또는 여러 별을 둘러싸는 데 필요한 다이슨 유닛의 개수를 구하는 것이다. 별마다 따로 원을 만드는 것이 아니라, 하나의 다이슨 원이 필요하다.

편의상 별과 다이슨 유닛은 모두 Intergalactic Coordinate System에 맞춰 정렬된, 정확히 $1$ 곱하기 $1$ 크기의 Intergalactic Unit 정사각형으로 모델링한다. 다이슨 유닛은 최소한 꼭짓점 하나를 공유하면 서로 연결된다. 예시는 그림 1을 참고하라.

그림 1: 입력 예제 1의 설명. 노란 정사각형은 네 개의 별이고, 점선으로 된 파란 정사각형은 별을 둘러싸는 최적의 다이슨 원이다. 나머지 흰 부분은 우주 공간의 빈 곳이다.

형식적으로 말하면, 평면의 일부 정사각형을 다이슨 유닛으로 선택하여, 나머지 정사각형을 inside 정사각형과 outside 정사각형으로 나눌 수 있어야 한다. 모든 별은 inside 정사각형에 있어야 한다. inside 정사각형들은 변을 통해 서로 연결된 하나의 영역을 이루어야 하며, 변을 통해 outside 정사각형과 이어져서는 안 된다. outside 정사각형들은 무한히 뻗어 나가는 하나의 연속된 영역을 이룬다.

첫 줄에 별의 개수를 나타내는 정수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어진다. 이어지는 $n$개의 줄에는 각각 별 중심의 위치를 나타내는 두 정수 $x$와 $y$ ($-10^6 \leq x, y \leq 10^6$)가 주어진다. 같은 위치에 있는 별은 없다.

입력된 모든 별의 에너지를 모으는 데 필요한 다이슨 유닛의 최소 개수를 출력한다.