25010번 - 지름길 서브태스크언어 제한함수 구현

$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좌표이다. 여러분은 이 함수를 사용하여 결과를 제출한다. 반환 값은 새롭게 건설된 도로가 추가될 때, 도시들의 지름의 최솟값이다.

여러분은 shortcut.cpp라는 이름의 정확히 하나의 파일을 제출해야만 한다. 이 파일에는 다음의 함수가 구현되어야 한다.

long long shortcut(int N, long long X[], long long Y[]);

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론, 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

주어지는 grader는 다음과 같은 형식으로 입력을 읽는다:

• line $1$: N (N : 도시들의 개수, $3 ≤ $N$ ≤ 250\,000$)
• line $2$ ~ ($N+1$): line $i$에 도시 $i-1$의 좌표 (x, y)를 나타내는 두 정수 x와 y ($-10^9≤ $x, y$ ≤ 10^9$)

주어지는 grader는 새롭게 건설된 도로가 추가될 때, 도시들의 지름의 최솟값을 출력한다.

• shortcut_public.tar