Manhattan( (x1,y1) , (x2,y2) ) = max(abs(p1 - p2), abs(q1-q2))

, p1 = x1 + y1, q1 = x1 - y1, p2 = x2 + y2, q2 = x2 - y2.

**source code**

import static java.lang.Math.abs;

import static java.lang.Math.max;

import static java.lang.Math.random;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class ManhattanDistance {

@Test

public void test0() {

for (int loop = 0; loop < 1e5; loop++) {

int d = (int) 1e8;

int x1 = randomInt(-d, d);

int y1 = randomInt(-d, d);

int x2 = randomInt(-d, d);

int y2 = randomInt(-d, d);

// definition Manhattan( (x1,y1) , (x2,y2) )

int manhattan = abs(x1 - x2) + abs(y1 - y2);

assertEquals(manhattan, abs(x1 - x2) + abs(y1 - y2));

// change to (p, q) = (x + y, x - y)

int p1 = x1 + y1;

int q1 = x1 - y1;

int p2 = x2 + y2;

int q2 = x2 - y2;

assertEquals(x1, (p1 + q1) / 2);

assertEquals(x2, (p2 + q2) / 2);

assertEquals(y1, (p1 - q1) / 2);

assertEquals(y2, (p2 - q2) / 2);

assertEquals(manhattan, abs((p1 + q1) / 2 - (p2 + q2) / 2) + abs((p1 - q1) / 2 - (p2 - q2) / 2));

// factor

assertEquals(manhattan, (abs((p1 + q1) - (p2 + q2)) + abs((p1 - q1) - (p2 - q2))) / 2);

int p = p1 - p2;

int q = q1 - q2;

assertEquals(manhattan, (abs(p + q) + abs(p - q)) / 2);

int absQ = abs(q);

assertEquals(manhattan, (abs(p + absQ) + abs(p - absQ)) / 2);

assertEquals(manhattan, (abs(p + absQ) + abs(-(p - absQ))) / 2);

assertEquals(manhattan, (abs(absQ + p) + abs(absQ - p)) / 2);

int absP = abs(p);

assertEquals(manhattan, (abs(absQ + absP) + abs(absQ - absP)) / 2);

assertEquals(manhattan, (absQ + absP + abs(absQ - absP)) / 2);

if (absP > absQ) {

assertEquals(manhattan, (absQ + absP + (absP - absQ)) / 2);

assertEquals(manhattan, absP);

} else {

assertEquals(manhattan, (absQ + absP + (absQ - absP)) / 2);

assertEquals(manhattan, absQ);

}

assertEquals(manhattan, max(abs(p), abs(q)));

}

}

private static int randomInt(int min, int max) {

return min + (int) (((max + 1) - min) * random());

}

}

## コメント