최적의 장소
면접 대비시간 제한1초메모리 제한512 MB
N개의 점이 주어질 때, 각 참가자까지의 맨해튼 거리 합을 최소로 하는 정수 좌표 (X, Y)를 구한다.
문제
IOI 2020은 싱가포르 국립대학교(NUS) 컴퓨팅 스쿨이 주최하고, 싱가포르 교육부(MOE)와 싱가포르 전시 컨벤션 뷰로(SECB)가 후원하여 싱가포르에서 열린다.
이렇게 큰 행사를 주최할 때의 어려움 중 하나는 행사에 적합한 장소를 찾는 것이다. 흔히 참가자들의 이동 거리를 줄이는 장소를 고르자는 제안이 나온다. 따라서 그러한 장소 하나를 찾는 프로그램을 작성해야 한다.
IOI 2020에 N명의 참가자가 있다고 하자. i번째 참가자의 집이 직교 좌표평면에서 (Xi, Yi)에 있다고 가정하자. 이동 거리의 총합이 최소가 되는 곳에 IOI 2020을 열 장소를 찾으려 한다. IOI 2020을 (X, Y)에서 열기로 했을 때, i번째 참가자의 이동 거리는 (X, Y)와 (Xi, Yi) 사이의 맨해튼 거리, 즉 |X − Xi| + |Y − Yi|이다.
이동 거리의 총합이 최소가 되는 장소가 여러 개라면, 그러한 좌표 중 아무거나 하나를 출력하면 된다. 행사 장소가 참가자의 집과 같은 위치여도 된다. 다만 행사는 X와 Y가 정수인 위치 (X, Y)에서 열려야 한다. 여러 참가자가 같은 좌표에 살 수도 있다. 이 경우 각자의 이동 거리를 따로 더한다. (각자 따로 이동한다고 가정한다.)
입력
첫 줄에 정수 N이 하나 주어진다. N은 참가자의 수이다.
이어서 N개의 줄이 주어지고, 각 줄에는 정수 2개가 있다. i번째 줄에는 Xi와 Yi가 주어진다. 이는 i번째 참가자의 집 좌표가 (Xi, Yi)임을 나타낸다.
출력
이동 거리의 총합이 최소가 되는 행사 장소의 좌표 (X, Y)를 나타내는 정수 2개를 한 줄에 공백으로 구분하여 출력한다.