標籤：

OI 演算法笛卡爾坐標系

曼哈頓距離與切比雪夫距離的轉換

01-26

0x00 寫在前面

在平面內，對於點 $P$ $(x_1,y_1)$ 與點 $Q$ $(x_2,y_2)$ 我們所遇到的常見的距離有三種：

歐幾里得距離 $(Euclidean;Metric)$ ： $sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ .
曼哈頓距離 $(Manhattan;Distance)$ ： $left| x_1-x_2 ight|+left| y_1-y_2 ight|$ .
切比雪夫距離： $(Chebyshev;Distance)$ : $max { left| x_1-x_2 ight|, left| y_1-y_2 ight|}$ .

0x01 幾何意義

很多時候，我們發現如果直接計算其中的某一個並不是很方便，於是便開始研究了一下它們的關係。

我決定從幾何意義入手：

考慮對於一個平面直角坐標系，距離原點曼哈頓距離為 $a$ 的點集組成了一個正方形的四條邊，四個頂點分別為： $(0,a),(a,0),(0,-a),(-a,0)$ .

考慮在同樣的一個平面直角坐標系中，距離原點切比雪夫距離為 $a$ 的點集構成了的另一個

正方形的四條邊，四個頂點分別為： $(a,a),(a,-a),(-a,-a),(-a,a)$ .

顯然，兩個正方形的邊長之比為 $1：sqrt{2}$ .

0x02 關於曼哈頓距離與切比雪夫距離的轉換

如何轉化呢，考慮旋轉這個圖形。

先考慮將曼哈頓距離轉化為切比雪夫距離：

將代表曼哈頓距離的正方形繞原點逆時針旋轉 $frac{pi}{4}$ ，我們發現兩個正方形現在是相似的。於是只要把代表曼哈頓距離的正方形擴大到原來的 $sqrt2$ 倍。

我們發現原來在代表曼哈頓距離的正方形的四條邊上的點 $A(x,y)$ 的坐標由旋轉之後變為了 $(xcdot cosfrac{pi}{4}-ycdot sinfrac{pi}{4},ycdot cosfrac{pi}{4}+xcdot sinfrac{pi}{4})$ （用向量很好推的），然後擴大後變為了 $A$ （若是順時針旋轉得到的是 $(x+y,x-y)$ ）

其實這裡的旋轉事實上可以理解為坐標軸的旋轉。

再考慮切比雪夫距離轉化為曼哈頓距離：

若由圖形旋轉的方法原來的點 $A(x,y)Rightarrow A$ .表示左邊的切比雪夫距離等於右邊的曼哈頓距離.

或者已知由曼哈頓距離轉化為切比雪夫距離的 $A(x,y) Rightarrow A$ ，我們從右反推到左得到 $A(x,y)Rightarrow A$ .

沒有圖好像不太清楚......不過不知道 $Linux$ 用什麼作圖......改天補上

0x03 結論

把一個坐標系的曼哈頓距離轉化為切比雪夫距離，則將每一個點 $A(x,y)$ 映射到 $A$ 或 $A$ .
把一個坐標系的切比雪夫距離轉化為曼哈頓距離，則將每一個點 $A(x,y)$ 映射到 $A$ 或 $A$ .

0x04 寫在後面

由一道題興起推來，水平有限，可能不太準確，若是有什麼不準確/有瑕疵的地方，希望指出，謝謝！

推薦閱讀：

※SDOI一輪摸魚記
※數論複習

TAG:笛卡尔坐标系 | OI | 算法 |