A rescue operation has n crews at integer coordinates on a grid. They must all travel to one common meeting point, which itself must have integer coordinates. The cost for a crew is the Manhattan distance from its position to the meeting point. Choose the meeting point that minimizes the sum of all crews' costs, and report that minimum total cost.
Line 1: an integer n, the number of crews.
Next n lines: two integers x y, the position of a crew.
A single integer: the minimum possible total Manhattan distance.
Example 1
Input
3 0 0 4 0 0 4
Expected
8
Explanation
Meeting at (0, 0) costs 0 + 4 + 4 = 8, and no integer point does better, so the answer is 8.
Example 2
Input
1 5 5
Expected
0
Explanation
With one crew the meeting point can be its own location, giving a total cost of 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →