34729번 - 팔정도 모니터링

팔정도의 모습

동국대학교 중심에는 팔정도가 있다. 팔정도는 총 여덟 방향으로 뻗어 있으며, 길은 네 직선 $x=0$, $y=0$, $y=x$, $y=-x$을 따라 나 있다.

팔정도에서는 매일 오전 8:30$\sim$9:00, 오후 5:40$\sim$6:00까지 라디오 방송을 한다. 방송 담당 채원이는 새 오디오 시스템의 공정성 테스트를 진행하려 한다. 이번 테스트의 목표는 같은 보폭으로 네 방향에 동시에 섰을 때, 네 지점의 청취 비용 합이 최소가 되도록 하는 것이다.

채원이는 각 길마다 모니터 인원 1명씩, 총 네 명을 배치한다. 네 사람은 동시에 같은 보폭 $t$로 걸어가 다음 네 지점에 선다:

$(t,0), (0,t), (t,t), (t,-t)$

여기서 $t$는 정수이며 $-R \le t \le R$ 범위 안에서만 선택할 수 있다.

현재 팔정도에는 총 $N$개의 스피커가 있다. $i$번째 스피커의 좌표는 $(x_i, y_i)$이다.

임의의 점 $P=(x_p,y_p)$에서의 "거리 기반 비용" $F(P)$는 모든 스피커까지의 맨해튼 거리의 합으로 정의한다:

$F(P)=\sum_{i=1}^{N}\bigl(|x_p-x_i|+|y_p-y_i|\bigr).$

우리는 하나의 $t$를 골라 네 지점의 비용 합

$G(t)=F(t,0)+F(0,t)+F(t,t)+F(t,-t)$

이 가장 작아지도록 하려 한다.

채원이를 도와 $G(t)$ 의 최솟값을 구해보자!

위는 스피커가 $(1, 2), (2, 1)$에 있을때의 예시를 나타낸 것이다. <그림2>를 보면 $t = 1$일 때 각 사람에 대해서 스피커까지의 맨해튼 거리의 합 즉,$G(1) = 16$으로 최소이다. 인접한 값 $t = 0, 2$에서는 각각 $G(0) = 24, G(2) = 18$로 더 크다. 따라서 최적의 선택은 $t = 1$이고 출력은 $16$이다.

첫째 줄에 두 정수 $N, R$이 주어진다. 다음 $N$개의 줄에 걸쳐 각 스피커의 좌표 $x_i, y_i$가 주어진다.

$G(t)$의 최솟값을 정수 하나로 출력한다.

• $1 \le N < 10^{5}$
• $1 \le R \le 10^{9}$
• $|x_i|, |y_i| \le 10^{9}$
• $x_i \ne 0$, $y_i \ne 0$, $x_i \ne y_i$, $x_i \ne -y_i$