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 *i*th of these lines will contain two space-separated
integers *x _{i} y_{i}*, giving the

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

3 3

The score for each input file will be 100% if a correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2023

Page generated: 24 March 2023, 8:54pm AEDT