Busy Bees#4322
There is an infinite beehive consisting of hexagonal cells. Some cells contain workers who deliver honey to the queen. At any moment, any cell can contain any number of bees. Workers can move only between neighboring (sharing an edge) cells, while the queen cannot move. The distance between two cells is the minimum number of steps for a worker to get from one cell to another. The workers are very busy, so they want to spend the least possible time traveling to the queen.
You are given the coordinates of different cells that contain workers; the coordinate system is shown below. Find the location for the queen so that the total distance the workers need to travel from their cells to hers is minimized.
The first line contains the number of workers (1 \leq N \leq 10^5). Each of the following lines contains two integers, the coordinates of workers' cells. Each coordinate does not exceed 10^9 by absolute value. All cells are distinct.
Output the coordinates of the required cell. If there are multiple solutions, output any of them.
Example 1