UHCC1 P4 - Manhattan Distance

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem types

Felim has N points with integer coordinates in the xy-plane that he received as a Valentine's gift, and he wants to find two distinct points A and B with integer coordinates such that the sum of the Manhattan distance between the N points and A and B is minimal.

He is unable to do so, so he wants you to find these two points and output the minimum distance.

The Manhattan distance between (x_1,y_1) and (x_2,y_2) is |x_1-x_2|+|y_1-y_2|.


1\leq N\leq 10^6

-10^9\leq x_i,y_i\leq 10^9

Input Specification

The first line contains the integer N. The next N lines each contain 2 integers, x_i, y_i.

Output Specification

The first and only line contains the minimum sum of the Manhattan distance from the N points to the two points you selected.

Sample Input

3 1
5 1
1 3
5 4

Sample Output


Explanation for Sample

If we choose the two points to be (3,3) and (4,2), then the sum of distances is 11+11=22. It can be proven that this is minimal.


There are no comments at the moment.