숨겨진 도토리
면접 대비시간 제한1초메모리 제한512 MB
N개의 격자 점 중 나머지 점까지의 맨해튼 거리 합이 최소인 점을 고르고, 동점이면 X가 작은 것, 그다음 Y가 작은 것을 출력한다.
문제
다람쥐 밥은 영역 안에 N개의 은신처를 만들어 겨울나기를 위한 도토리를 보관한다. 은신처는 격자의 정수 좌표에 놓여 있다. 밥은 그중 하나를 주거지로 정하려 한다. 다른 동물이 도토리를 먹어치울까 봐 걱정이 많기 때문이다. 따라서 주거지에서 나머지 N − 1개의 은신처까지 이어지는 길의 평균 거리가 최소가 되도록 주거지를 고르고 싶다.
밥은 방향 감각이 좋지 않다. 주거지와 각 은신처 사이에서 길을 잃지 않으려고, 밥은 정수 좌표의 가로선과 세로선만 따라 이동하기로 한다.
예를 들어 다음 격자에서 두 점 D와 E 사이의 거리는 4이고(D와 E 사이의 최단 경로 하나를 아래에 빨간색으로 표시했다), D와 나머지 점 사이의 평균 거리는 13/5이다.
입력
입력은 다음 줄들로 구성된다.
- 첫째 줄: 은신처의 총 개수 N, 정수이다.
- 다음 N개 줄: i번째 은신처의 정수 좌표 Xi와 Yi가 공백 하나를 사이에 두고 주어진다.
출력
다른 은신처까지의 거리를 최소화하는 은신처의 좌표를 출력한다. 동률일 때는 X 좌표가 가장 작은 은신처를 출력하고, 그래도 동률이면 Y 좌표가 가장 작은 은신처를 출력한다.
제한
- 1 ≤ N ≤ 1 000
- 모든 점에 대해 0 ≤ Xi, Yi ≤ 1 000 000
같은 좌표에 놓인 은신처는 없다.