|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
IOI 2020 will be held in Singapore, hosted by School of Computing of the National University of Singapore (NUS), supported by Singapore Ministry of Education (MOE) and Singapore Exhibition & Convention Bureau (SECB).
One of the challenges of hosting such a large event is to find a suitable location for the event. A common suggestion would be to select a location that reduces the travelling distance for the participants. You are thus tasked to write a program to find one such location.
Suppose there are N participants for IOI 2020. Assume the i th participant’s house is located on (Xi , Yi) on the cartesian plane. You aim to find a location to hold IOI 2020 such that the total sum of travelling distance is minimized. Assume IOI 2020 is chosen to be at (X, Y), the travelling distance for the i th participant is the Manhattan distance between (X, Y) and (Xi, Yi), i.e., |X − Xi| + |Y − Yi|.
If there are multiple locations where the total sum of travelling distance is minimized, you are to output any one of these coordinates. It is possible for the location of the event be the same as the location of 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 1 participant lives at the same coordinates. In that case, you are to sum their travelling distance separately. (Assume they will travel separately.)
The input will start with a single integer, N, in a single line. N denotes the total number of participants.
N lines will then follow with 2 integers each, the ith line will contain Xi and Yi. This indicates that the coordinate of the ith participant’s house is at (Xi, Yi).
Output 2 integers (X, Y) on the same line, space separated. (X, Y) will denote the coordinates of the event where by the total sum of travelling distance would be minimized.
2 1 0 4 0
Note that this is not the only output that would be accepted. In particular, the following alternative outputs will also be accepted for Sample Testcase 1.
Regardless of whether we choose (1, 0),(2, 0),(3, 0) or (4, 0), the sum of total travelling distance will still be 3.
6 1 0 3 0 5 0 7 0 9 0 11 0
Note that this is not the only output that would be accepted. In particular, the following alternative outputs will also be accepted for Sample Testcase 2.
9 1 16 3 12 5 6 7 10 9 8 11 4 13 14 15 2 17 18