Hacker News Reader

The conversion from the given metric to the 'taxicab' metric needs some justification!

Else use just the n^2 approach or, if really want to struggle for something faster, then use my convexity approach.

There may be another approach if can find a cute way to exploit the special properties of that special metric.

The taxicab metric is useful here because if you compute the components of a distance in the square metric, you must max() them together, while under the taxicab metric you can add them together. We can add a pair of large sums together to get the large sum of pairs, but we can't max() a pair of large sums together to get the large sum of max()es.

One way to get to the taxicab metric verson of the problem is to take w = x + y and z = x - y. From then on all the distances you calculate in wz-space under the taxicab metric will be precisely twice the distance between the same points in xy-space under the square metric.

Nice! Then, if all this is correct, your solution should be nicely fast. Cute conversion of the metrics!

Reply on news.ycombinator.com