關于曼哈頓距離和切比雪夫距離的轉換和應用

看到曼哈頓距離就不難想到可以與切比雪夫距離進行轉換。

切比雪夫距離：

　　平面上兩個點$(x1，y1),(x2，y2)$ 之間的距離為$max(|x1-x2 | , | y1 - y2 |)$.

如何轉換呢？考慮把原來的坐标系旋轉45°，原來的坐标$(x,y)$就變成了$(x+y，x - y )$

然後原圖上兩點的曼哈頓距離就變成了切比雪夫距離了。

在轉換之後，我們就可以轉化成對于兩個點其中一維的內插補點剛好為D，另一次元為<=D

為了友善讨論，我們先假設x內插補點為D，

這樣來讨論：

$x1−x2=D$

$−D≤y1−y2≤D$

我們固定了一維x，那麼另外一維y就處于一個範圍内，我們就可以快速的處理每一個點有多少與之曼哈頓距離為D的節點了。

具體實作是按照x排序，如果x相同就按照y排序。

然後我們隻需要找一個點x的兩個距離為D的點，$x+D$和$ x-D$，對應有多少個y之差小于等于D