Yet Another Convex Hull Problem

모든 점의 $x$좌표 중 최솟값과 최댓값을 각각 $\min x_i$, $\max x_i$라고 하자. 모든 점의 $y$좌표 중 최솟값과 최댓값도 각각 $\min y_i$, $\max y_i$라고 하자.

도형이 모든 점을 포함하므로, 도형은 $x$좌표가 $\min x_i$인 점과 $x$좌표가 $\max x_i$인 점을 모두 포함해야 한다. 따라서 도형의 경계를 따라 한 바퀴 돌 때, 오른쪽으로 이동한 총 길이는 적어도 이상이다. 닫힌 도형이므로 왼쪽으로 이동한 총 길이도 오른쪽으로 이동한 총 길이와 같다. 따라서 가로 방향 선분들의 길이 합은 적어도 이다.

같은 이유로 세로 방향 선분들의 길이 합은 적어도 $2(\max y_i-\min y_i)$이다.

따라서 어떤 맨해튼 컨벡스 헐의 둘레도 다음 값보다 작을 수 없다.

$$2\left((\max x_i-\min x_i)+(\max y_i-\min y_i)\right)$$

이 값은 모든 점을 포함하는 축에 평행한 직사각형을 고르면 실제로 만들 수 있다. 그러므로 이 값이 정답이다.

정답은 $32$비트 정수 범위를 넘을 수 있으므로 $64$비트 정수를 사용해야 한다.

시간 복잡도는 $O(N)$이다.