지름길

$N$개의 도시들이 평면 위의 서로 다른 곳에 위치한다. 이 도시들은 $1$부터 $N$까지 정수로 나타낸다.

도시 $i$와 도시 $i+1$사이에는 도로가 존재하고 $R\_i$로 나타낸다($i = 1 , \dots , N-1$). 따라서 모두 $N-1$ 개의 도로들이 존재한다. 각 $i = 1 , \dots , N-1$ 에 대해서, 도시 $i$가 위치하고 있는 좌표를 $(x\_i,y\_i)$로 나타내면, 도로 $R\_i$의 길이는 $\left| x\_i - x\_{i+1} \right| + \left| y\_i - y\_{i+1} \right|$로 주어진다.

도시 $i$와 $j$사이의 경로 $P$는 $i$로부터 $j$로 이동할 때 지나는 도로들의 집합이다. 경로 $P$의 길이는 $P$에 속한 도로들의 길이의 합이다. 우리는 도시들의 지름에 관심이 있다. 지름은 모든 도시간의 최단 경로들의 길이의 최댓값이다. 물론 위에 주어진 도시들의 지름은 도시 $1$과 $N$사이 경로의 길이와 같다.

우리는 위의 도시들 중 한 쌍을 선택해서 두 도시 사이에 새롭게 도로를 건설할 예정이다. 이 도로를 $R\_\text{new}$로 나타내고, $R\_\text{new}$가 도시 $a$와 $b$를 연결한다면, $R\_\text{new}$의 길이는 $\left| x\_a - x\_b \right| + \left| y\_a - y\_b \right|$ 로 주어진다. 문제는 도시들의 지름이 최소가 되도록 도로 $R\_\text{new}$를 결정하는 것이다.

$N$개 도시들의 위치가 주어질 때, 도시들의 지름이 최소가 되도록 도로 $R\_\text{new}$를 결정하고 그 지름의 최솟값을 출력하는 프로그램을 작성하시오.

예를 들어, 아래 그림에서 $4$개의 도시와 도시사이를 연결하는 $3$개의 도로(실선)가 주어진다. 새롭게 건설할 수 있는 도로의 후보는 $3$개($1$과 $4$사이, $1$과 $3$사이, $4$와 $2$사이)가 존재한다. 이 중에서 그림처럼 $4$와 $2$사이에 도로(점선)를 건설하면 도시들의 지름은 $6$이고 이것이 최솟값이다.

여러분은 관리자를 위해 다음 한 가지 함수를 구현해야만 하고, 이 함수를 사용하여 답을 제출하여야 한다.

• long long shortcut(int N, long long X[], long long Y[]); 도시들의 개수 N, 각 도시의 위치를 나타내는 X[0..N-1]와 Y[0..N-1]를 인자로 받는다. 여기서, X[]와 Y[]는 크기 N인 벡터(vector)이고, X[i]와 Y[i]의 값은 각각 도시 i+1의 x좌표와 y좌표이다. 여러분은 이 함수를 사용하여 결과를 제출한다. 반환 값은 새롭게 건설된 도로가 추가될 때, 도시들의 지름의 최솟값이다.