DISTANCE - Manhattan
The L1 distance of two d-dimensional points is the sum of absolute values of their coordinate differences (i.e. Σi=1d |xi - yi| for two points x,y). Given N points in the plane you must find the farthest pair of points under the L1 distance metric and output their distance.
Input
The first line of the input is "N d" (2 ≤ N ≤ 100000, 1 ≤ d ≤ 6) signifying that there are N points in d-dimensional space. N lines then follow, where the ith line is a space-separated list of d numbers, the coordinates of the ith point. All given coordinates are integers that are at most 1000000 in absolute value, and all given points are distinct.
Output
Your output should consist of a single integer, the farthest distance between a pair of input points, followed by a newline.
Example
Input: 3 2 0 0 -5 0 1 1 Output: 7
hide comments
toemmsche:
2020-07-01 23:26:28
Surprised my solution was accepted immediately, very cool problem |
|
Sudarshan K:
2015-05-28 17:18:59
Nice problem :) |
Added by: | Minilek |
Date: | 2008-01-10 |
Time limit: | 1s-4.446s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT 1st Team Contest 2007 |