Best Place
InterviewTime limit1sMemory limit512 MB
Given N points, find integer coordinates (X, Y) that minimize the sum of Manhattan distances from the point to every participant.
Problem
IOI 2020 will be held in Singapore, hosted by the School of Computing of the National University of Singapore (NUS) and supported by the Singapore Ministry of Education (MOE) and the Singapore Exhibition & Convention Bureau (SECB).
One challenge of hosting such a large event is finding a suitable location. A common suggestion is to pick a location that reduces the travelling distance for the participants. You are tasked with writing a program that finds one such location.
Suppose there are N participants for IOI 2020. Assume the i-th participant's house is located at (Xi, Yi) on the Cartesian plane. You want to find a location for IOI 2020 that minimizes the total travelling distance. If IOI 2020 is held at (X, Y), the travelling distance for the i-th participant is the Manhattan distance between (X, Y) and (Xi, Yi), that is, |X − Xi| + |Y − Yi|.
If multiple locations minimize the total travelling distance, output any one of those coordinates. The event location may coincide with a participant's house. However, the event must be held at a position (X, Y) where X and Y are integers. It is also possible that more than one participant lives at the same coordinates. In that case, sum their travelling distances separately. (Assume they travel separately.)
Input
The input starts with a single integer N on one line. N is the total number of participants.
N lines follow, each with 2 integers. The i-th line contains Xi and Yi, meaning that the coordinate of the i-th participant's house is (Xi, Yi).
Output
Output 2 integers (X, Y) on the same line, separated by a space. (X, Y) is the coordinate of the event location that minimizes the total travelling distance.