Cannot solve it in contest, and Hackson solve this afterwards.
The idea is observing that in Manhattan distance, the absolute value |x1-x2| can be rewrite as (x1-x2) or (x2-x1). We can do exhaustion on the sign of each dimension, sum up the value of each dimension, and find the maximum and minimum. The maximum difference between them for all cases would be the answer.
An interesting and useful technique to due with problems with absolute values or manhattan distance.
沒有留言:
張貼留言