문제
정올시에 어떤 대규모 박람회가 개최가 결정되었다.
이번 박람회에는 2개의 테마가 있고, 정올시에 있는 N개의 전시시설에서 각각 2개의 테마중에 하나를 골라 전시할 예정이다.
시설의 위치는 평면좌표 (x, y)로 표현한다.
위치 (x, y)에 있는 시설에서 (x', y')에 있는 시설까지 이동하는데는, |x-x'|+|y-y'|만큼의 시간이 걸린다. (정수 a에 대해서, |a|는 절대값을 의미한다.)
동일 테마의 전시내에서 통일감을 내고, 한쪽의 테마만 관심을 가진 사람들이 불편하지 않도록 같은 테마를 전시하는 시설사이의 이동거리를 가능한한 짧게 나누려고 한다.
전시를 나누는 방법은 모든 전시의 테마를 같게 하는 것을 제외하고 모든 경우가 가능하다. 같은 테마를 가지는 전시하는 2개의 시설간의 이동시간의 최대를 M이라한다.
N개의 전시시설이 위치를 나타내었을때 전시들의 테마를 알맞게 나눴을 경우 M의 값이 최소값을 구하는 프로그램을 작성해라.
입력
입력의 첫째 줄에는 시설의 개수 N(3≤N≤100,000)가 써있다.
입력의 i+1행 (1≤i≤N)에는 각 시설의 위치를 나타내는 2개의 정수 xi, yi (|xi|≤100,000, |yi|≤100,000)가 공백으로 구분되어 적혀 있으며,
이는 i번째 시설의 좌표가 (x, y)라는 것을 나타낸다. 같은 좌표에 두개 이상의 시설이 존재하는 경우는 없다.
출력
동일한 테마의 전시를 하고있는 두개의 시설간의 이동시간의 최대값 M의 최소값을 한줄에 출력해라.
예제
5
0 0
1 0
-1 -2
0 1
-1 1
3
이 경우에, 만약 좌표 (0,0),(1,0),(0,1)에 한쪽의 테마로, (-1,-2),(-1,1)을 다른 한쪽의 테마로 나누면, 같은 테마를 전시하는 두개의 시설간의 이동시간이 모두 3이하가 된다.
이동시간을 모두 2이하가 되게 하는 것은 불가능함으로, 3을 출력한다.
로그인해야 코드를 작성할 수 있어요.