버스 터미널
시간 제한5초메모리 제한128 MB
격자 위의 N개 정류장 중 두 중심 정류장을 고르고 나머지를 하나씩 배정해서, 정류장 쌍 사이의 최대 경로 거리를 최소화하는 값을 구합니다.
문제
용인시는 정사각형 격자 위에 놓인 N개의 버스 정류장을 이용해 노선을 만들려고 한다. 정류장 중 두 곳을 중심 정류장 H1, H2로 고른다. 두 중심 정류장은 서로 직접 연결되고, 나머지 각 정류장은 H1 또는 H2 중 정확히 한 곳에 직접 연결된다.
두 지점 (x1, y1), (x2, y2)의 기본 거리는 |x1 - x2| + |y1 - y2|이다. 같은 중심 정류장에 연결된 두 정류장 사이의 노선 거리는 두 정류장에서 그 중심 정류장까지의 기본 거리의 합이다. 서로 다른 중심 정류장에 연결된 두 정류장 사이의 노선 거리는 첫 정류장에서 자기 중심 정류장까지의 거리, 두 중심 정류장 사이의 거리, 다른 중심 정류장에서 두 번째 정류장까지의 거리의 합이다.
두 중심 정류장과 각 정류장의 연결 방식을 적절히 정해, 서로 가장 멀리 떨어진 두 정류장 사이의 노선 거리를 최소화하려고 한다. 가능한 최소값을 구하라.
입력
첫째 줄에 정류장 수 N (2 <= N <= 500)이 주어진다. 다음 N개의 줄에는 각 정류장의 좌표 x, y가 주어진다. x는 가로 좌표, y는 세로 좌표이다. 모든 좌표는 5000 이하의 자연수이며, 어떤 두 정류장도 같은 위치에 있지 않다.
출력
서로 가장 멀리 떨어진 두 정류장 사이의 노선 거리로 만들 수 있는 최솟값을 나타내는 정수 하나를 출력한다.