A courier network has n depots at integer coordinates on a city grid (two depots may share the exact same location). The travel cost between two depots is their Manhattan distance |x1 - x2| + |y1 - y2|. Report the smallest travel cost over all pairs of distinct depots (by index). If two depots coincide, that smallest cost is 0.
Line 1: an integer n, the number of depots.
Next n lines: two integers x y, the coordinates of a depot.
A single integer: the minimum Manhattan distance over all pairs.
Example 1
Input
3 0 0 3 4 1 1
Expected
2
Explanation
Distances are (0,0)-(1,1)=2, (0,0)-(3,4)=7, (1,1)-(3,4)=5. The minimum is 2.
Example 2
Input
2 0 0 5 0
Expected
5
Explanation
The only pair is 5 units apart along the x-axis, so the answer is 5.
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 →