Answer to Question #309411 in Functional Programming for Akash srivastava

Question

Camp Setup (Contest)

Time Limit: 2 sec

Memory Limit: 128000 kB

Problem Statement

Given N points on 2D plane, you have to setup a camp at a point such that sum of Manhattan distance all the points from that point is minimum. If there are many such points you have to find the point with minimum X coordinate and if there are many points with same X coordinate, you have to minimize Y coordinate.

Manhattan distance between points (x1, y1) and (x2, y2) = |x1 - x2| + |y1 - y2|.

Input

First line of input contains N.

Next N lines contains two space separated integers denoting the ith coordinate.

Constraints:

1 <= N <= 100000

1 <= X[i], Y[i] <= 1000000000

Note:- the camp can overlap with the given points and the given points can also overlap(you have to consider overlapping points separately).

Output

Print two space separated integers, denoting the X and Y coordinate of the camp.

Example

Sample Input

3

3 3

1 1

3 2

Sample Output

3 2

Answer 1

It's been a while since this question is posted here. Still, the answer hasn't been got. Consider converting this question to a fully qualified assignment, and we will try to assist. Please click the link below to proceed: Submit order