Earlier quoted context omitted.
Exactly. I did just this, and still my algorithm supposedly gets only 4/15 test cases correct. The algorithm is pretty simple, and I tested it extensively against the naive O(n^2) algorithm on a bunch of random test cases and it always prints the same thing, so I'm not sure where it's going wrong. My one consolation is that no one else seems to have solved it either yet... Ah, the joy and frustration of programming c…
The conversion from the given metric to the 'taxicab' metric needs some justification! The n^2 algorithm is simple enough to be solid. If your code does not give their answers, then their answers might be wrong! My work with convexity is an effort at faster code, but actually programming all that would be a bit much. I've done such things, but I got the linear programming from the old IBM Fortran Optimization Subrout…
As for the justification, it shouldn't be too hard to show with a little algebra that
TaxicabDistance(x1+y1, y1-x1, x2+y2, y2-x2)/2 = ChebyshevDistance(x1, y1, x2, y2)
where
ChebyshevDistance(x1, y1, x2, y2) = max(|x1-x2|,|y1-y2|) and
TaxicabDistance(x1, y1, x2, y2) = |x1-x2|+|y1-y2|.