지름길

시간 제한3초메모리 제한1024 MB

요약

맨해튼 거리로 이어진 N개 도시의 사슬이 주어질 때, 도로 하나를 추가해 지름을 최소로 만드는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 투 포인터, 누적 합, 기하, 배열
정답자: 아직 제출이 없습니다

문제

$N$ 개의 도시가 평면 위의 서로 다른 위치에 있다. 도시는 1부터 $N$ 까지 정수로 번호가 매겨진다.

도시 $i$ 와 도시 $i+1$ 을 잇는 도로 $R_i$ 가 있다( $i = 1, \dots, N-1$ ). 도로는 모두 $N-1$ 개이다. 도시 $i$ 의 좌표를 $(x_i, y_i)$ 라 하면, 도로 $R_i$ 의 길이는 $|x_i - x_{i+1}| + |y_i - y_{i+1}|$ 이다.

도시 $i$ 와 도시 $j$ 사이의 경로 $P$ 는 $i$ 에서 $j$ 로 이동할 때 지나는 도로들의 집합이다. 경로 $P$ 의 길이는 $P$ 에 속한 도로들의 길이의 합이다. 지름은 모든 도시 쌍 사이 최단 경로 길이의 최댓값이다. 위에 주어진 도로에서는 지름이 도시 1과 $N$ 사이 경로의 길이와 같다.

두 도시를 골라 그 사이에 새 도로 $R_{\text{new}}$ 를 하나 건설한다. $R_{\text{new}}$ 가 도시 $a$ 와 $b$ 를 잇는다면 길이는 $|x_a - x_b| + |y_a - y_b|$ 이다. 도시들의 지름이 최소가 되도록 $R_{\text{new}}$ 를 정하고, 그 최솟값을 구하라.

구현

다음 함수를 구현한다. 채점 프로그램이 이 함수를 사용해 답을 받는다.

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

N은 도시의 수이다. X[i]와 Y[i]는 도시 i+1의 x좌표와 y좌표이다. 함수는 새 도로가 추가되었을 때 지름의 최솟값을 반환한다.

예제2

예제 1
입력
```
4
1 2
2 2
2 1
1 1
```
예상 출력
```
2
```
예제 2
입력
```
4
1 2
3 3
4 1
2 3
```
예상 출력
```
6
```