난민

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

요약

각 난민이 (x, y)에 도착할 때마다, 강 x = 0 위에서 처음 i명의 난민까지 맨해튼 거리 합을 최소로 하는 y좌표와 그 최소 합을 구한다.

문제

A나라에서 내전이 일어났다.

그 때문에 많은 내전 난민이 B나라로 오게 되었고, B나라는 이들을 위해 난민촌을 건설해 주었다.

다음은 난민촌을 좌표평면으로 나타낸 그림이다. 파란색 선은 강, 빨간색 점은 난민의 거주 위치를 나타낸다.

난민촌에는 직선 (x=0)을 따라 흐르는 강이 하나 있다.

물을 얻으려면 이 강을 이용해야 하는데, 수질이 좋지 않아 정수시설을 설치하려고 한다.

하지만 예산 문제로 정수시설은 강의 한 지점에만 설치할 수 있기 때문에, 각 난민이 정수시설까지 이동하는 거리의 합이 최소가 되는 위치에 정수시설을 설치하려고 한다.

지금 이 순간에도 난민이 이주해 오고 있다. 난민촌에 사람들이 이주해 올 때마다, 정수시설을 설치해야 하는 위치와 그때의 이동거리의 합을 갱신해 알려주자.

두 좌표 ((x_1, y_1))와 ((x_2, y_2)) 사이의 거리는 (|x_1 - x_2| + |y_1 - y_2|)로 계산한다.

첫째 줄에 난민의 수 (N)이 주어진다.

이어서 (N)개의 줄에, (i)번째로 이주해 온 난민의 위치 ((x_i, y_i))가 공백으로 구분되어 주어진다.

문제의 답을 공백으로 구분하여 (N)줄에 걸쳐 출력한다.

(i)번째 줄에, (1)번째부터 (i)번째까지 이주해 온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 (y)좌표와, 그때의 이동거리의 합을 공백으로 구분하여 출력한다.

만약 이를 만족하는 정수시설의 위치가 여러 곳이라면, (y)좌표가 가장 작은 지점을 출력한다.