- Practice
- Mathematics
- Geometry
- Meeting Point

# Meeting Point

# Meeting Point

There is an infinite integer grid where **N** people live in **N** different houses. They decide to create a meeting point at one person's house.

From any given cell, all 8 adjacent cells can be reached in 1 unit of time, e.g. (x,y) can be reached from (x-1,y+1) in one unit of time. Find a common meeting place which minimizes the combined travel time of everyone.

**Input Format**

A positive integer N that denotes N houses or people.

The following *N* lines will contain two integers x,y each that denote the coordinates of the respective house.

**Output Format**

An integer, **M**, that denotes the minimum combined travel time of everyone.

**Constraints**

N <= 10^{5}

The absolute value of each co-ordinate in the input will be at most 10^{9}

**HINT:** You may need 64-bit integer.

**Input #1**

4 0 1 2 5 3 1 4 0

**Output #1**

8

**Explanation**

The houses will have a travel-sum of 11, 13, 8, or 10. 8 is the minimum.

**Input #2**

6 12 -14 -3 3 -14 7 -14 -3 2 -12 -1 -6

**Output #2**:

54