平面距離
介紹¶
-
歐幾里德：\(\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}\)
-
曼哈頓（計程車幾何）：\(|x_i - x_j| + |y_i - y_j|\)
-
切比雪夫：\(\max(|x_i - x_j|, |y_i - y_j|)\)
轉換¶
先來看圖
-
曼哈頓 ⇒ 切比雪夫
-
\((x,y)\Rightarrow (x+y,x-y)\)
-
原本座標的曼哈頓距離 = 新座標中的切比雪夫距離
-
-
切比雪夫 ⇒ 曼哈頓
-
\((x,y)\Rightarrow (\frac{x+y}{2},\frac{x-y}{2})\)
-
原本座標的切比雪夫距離 = 新座標中的曼哈頓距離
-
例題¶
IOI 2007 Pairs
有一個盤面大小為 \(m\)，給 \(n\) 個 \(B\) 座標點 \(p_i\)，問有幾對 \((i,j)\) 使曼哈頓距離 \(dis(p_i,p_j)\) 不超過 \(D\)
\(B\in \{1,2,3\}, n\le 10^5,m\le \{7.5\times 10^7, 7.5\times 10^4, 75\}\)
思路
一維: two pointer
二維: sweep line
-
(x-d, y) ⇒ +1
-
(x, y) ⇒ query[y-d, y+d]
-
(x+d, y) ⇒ -1
三維: m^2 枚舉 z，變二維的問題，注意自己會算到自己，所以答案要減 n
JOI 2023 Advertisement 2
一維座標上，有 \(n\) 個點，第 \(i\) 個點在 \(x_i\)，影響力為 \(e_i\)。若選擇一個點 \(i\)，能覆蓋點 \(j\) 若且唯若 \(|x_i-x_j| \le e_i - e_j\)，問最少要選幾個點才能使所有點都被覆蓋
\(n\le 5\times 10^5, 1\le x_i, e_i\le 10^9\)
思路
想成在二維座標平面上的點 \((x_i, e_i)\)，會發現要選的區域恰好是
轉 45 度後，問題就變成，有選的點會覆蓋左下，至少要選幾個點才能使全部被覆蓋。會發現答案就是從 x 左往右看過去 y 座標遞減的一些點，可用單調 stack 維護
2023 YTP 13_結束樂團出遊！(Kessoku_Band_at_Enoshima)
給 \(n\) 個二維座標點，點跟點之間的距離為曼哈頓距離，有 \(q\) 筆操作:
-
\(\text{query}(x,y):\) 問離 \((x,y)\) 最近的點的距離
-
\(\text{insert}(x,y):\) 在 \((x,y)\) 上加入一個新的點
\(n,q\le 3\times 10^5, |x|,|y| \le 5\times 10^4\)
思路
沒有 insert 的 subtask:
假如目前的點是 \(j\)，答案在 \(i\)，考慮 \(|x_i-x_j|+|y_i-y_j|\)，假如 \(x_i \ge x_j\) 且 \(y_i \ge y_j\)，那麼其實可以看成 \((x_i+y_i)-(x_j+y_j)\)，所以可以用掃描線，每個點的權值設為 \((x_i+y_i)\) 即可。
題解: https://hackmd.io/IiUWbMv1TNq07XBxTuXibA?view#Kessoku-Band-at-Enoshima