Hermione has finally convinced Harry to hold meetings for Dumbledore’s Army again, yay! Sadly, the Room of Requirement is not an option, as it has been compromised. Instead, Harry must determine where the best new meeting place is, considering all n members of the D.A. are at different locations on a grid. Out of sheer laziness, Harry plans to have the D.A. meet at one of these n locations.
The best meeting point is defined as the one that minimizes the sum of King distances between the chosen location and the other n-1 points. The King distance between two points is defined as the number of steps it takes to go from one point to the other, at each step travelling to one of the 8 surrounding lattice points (much like a King on a chessboard). For example, it takes one step to go from (0, 0) to the points (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), and (-1,1).
Math was never Harry’s strong point, so he’s having trouble figuring out where to meet. Can you help him?
The best meeting point is defined as the one that minimizes the sum of King distances between the chosen location and the other n-1 points. The King distance between two points is defined as the number of steps it takes to go from one point to the other, at each step travelling to one of the 8 surrounding lattice points (much like a King on a chessboard). For example, it takes one step to go from (0, 0) to the points (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), and (-1,1).
Math was never Harry’s strong point, so he’s having trouble figuring out where to meet. Can you help him?
Input Format
The first line contains an integer n representing the number of meeting points. The next n lines each contains two integers x y representing the coordinates of the possible meeting points.
Sample Input
2
1 1
1 2
Output Format Print the minimum total King distance of the best meeting point
Sample Output
1You must be logged in to submit a solution.