It is well known that given points (x, y) and you need to calculate the Manhattan distances between them, instead of using |x1-x2|+|y1-y2| you can first convert all points (x, y) into (x+y, x-y) and the distances will become max(|x1-x2|, |y1-y2|) (also known as Chebyshev distance). Can this trick apply to higher dimensions?

Oh, interesting trick. Can you give me a link to a problem that can be solved using this trick?

https://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d https://www.codechef.com/problems/TELEPORT

Codeforces Round #468 Div1D

Oh, thanks! I solved this problem, But it's not about max(|x1-x2|, |y1-y2|)

Actually it is.

sanya, luchshe sotku verni

Yes, it can be extended to n number of dimensions as seen in this problem http://www.spoj.com/problems/DISTANCE/.

6 Dimensions possible using all possible combinations of + — in place of |x1-x2|+|y1-y2|+...+|h1-h2| My accepted solution: https://ideone.com/obsrth

Well, the unit circles in and are both squares (although one of them rotated and shrinked by ) and therefore isomorphic as stated in the question.

But, the unit circle in is an octahedron, while the unit circle in is just a regular cube. I don't see an elementary formal proof that this implies that there isn't a bijection with wanted properties in dimensions higher than 2, but intuitively it seems that this is the reason the trick doesn't work in higher dimensions.

That's a nice way to see it! Maybe someone who deals with topology can help here? There may be some kind of non-trivial isomorphism between the 2 spaces (not exactly the aforementioned manhattan distance one).

IOI 2007 pairs. As I can remember, to solve this problem you should consider 4D space. Transform point (x, y, z) to the point (x + y + z, x + y — z, x — y + z, -x + y + z).