30394번 - 회전하지 않는 캘리퍼스

문제

버니어 캘리퍼스(Vernier Calipers)는 길이나 높이, 너비 등 기계류 또는 사람의 신체 부위 치수를 정밀하게 측정하는 자의 일종이다. 자 부분과 날 부분으로 구성되어 있으며, 두 날 부분 사이에 물건을 끼워 너비를 잰다. 재휘는 알고리즘 수업 시간에 기하학 알고리즘 중 볼록 껍질에서 사용되는 '회전하는 캘리퍼스' 알고리즘을 배웠다. 그런데 알고리즘을 있는 그대로 받아들인 재휘는 문득 캘리퍼스를 껍질 주위로 돌리는 것이 매우 어려운 일이라는 사실을 깨달았다. 그래서 재휘는 좀 더 쉬운 회전하지 않는 캘리퍼스 알고리즘을 고안해냈다.

회전하지 않는 캘리퍼스 알고리즘은 다음과 같다. 먼저, 한 평면 위의 점 $N$개가 주어진다. 그다음 캘리퍼스를 측정하고자 하는 점의 집합과 동일한 평면에 놓고 자 부분이 $y$축과 평행하도록 세운다(날 부분이 $x$축과 평행하게 한다). 이후 캘리퍼스의 날을 충분히 크게 벌리고 조금씩 좁혀가며 날이 점에 닿게 되면 멈춘다. 이때, 캘리퍼스의 크기는 충분히 크고, 캘리퍼스가 측정한 거리 값이 실행 결과가 된다.

이제 회전하지 않는 캘리퍼스 알고리즘을 구현해 보자.

입력

첫 번째 줄에 점의 수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 점들의 좌표 $x_i, y_i$가 공백으로 구분되어 주어진다. 점들의 좌표값은 모두 정수이다.

출력

캘리퍼스로 측정한 거리 값을 출력한다.

제한

• 3ドル \le N \le 2413$
• $-10^9 \le x_i, y_i \le 10^9 (1\le i \le N)$

노트

2413은 재휘의 학번이다.