Want to try solving this problem? You can submit your code online if you log in or register.
Input File: spiesin.txt
Output File: spiesout.txt
Time Limit: 0.1 second
Memory Limit: 64 Mb
You are the technical assistant for a group of MI6 spies operating in the remote location of Burgmanistan. The spies need a way of communicating without being noticed. You have devised a cunning method involving a drop point with a Palm Pilot hidden in a rock, but there is some disagreement amongst the spies about where the rock should be located.
To be fair to all spies, you want to minimise the sum of all distances that each spy has to travel to reach the drop point. All the roads in Burgmanistan are either straight north-south or straight east-west, and so spies must only travel in these directions in order to avoid suspicion.
As an example, suppose that Burgmanistan were laid out on a large coordinate grid as illustrated below, with three spies in positions (1,3), (3,5) and (4,1). The best location for the drop point is at (3,3) — here the spy at (1,3) has to travel two units east, the spy at (3,5) has to travel two units south, and the spy at (4,1) has to travel two units north and one unit west. The total travel distance in this example is 2+2+2+1 = 7, which is the smallest possible.
The first line of input will contain the integer n, giving the number of spies in your group (1 <= n <= 100,000).
Following this will be n lines, describing the locations of these n spies. The ith of these lines will contain two space-separated integers xi yi, giving the x and y coordinates of the ith spy (0 <= xi,yi <= 20,000).
Your program should output a single line containing two integers x y, separated by a single space, giving the x and y coordinates of where you should locate the drop point. If there is more than one best possible location, your program may output any such location.
3 1 3 3 5 4 1
The score for each input file will be 100% if a correct answer is written to the output file, and 0% otherwise.
© Australian Mathematics Trust 2001-2023
Page generated: 3 June 2023, 3:06pm AEST