[理工] 演算法 the closest pair 的問題

[sooge (喜歡平井桃)]

https://i.imgur.com/rQvFQL8.jpg

我想請問一下這題 the closest pair的問題

它的先前準備已經先將所有點依照y座標排序
那請問為什麼不依照x座標排序？

如果是掃點的話從下面掃上來
和由左邊掃到右邊應該結果是一樣的吧

不是都是依序抓距離分隔線距離小於d的點出來(假設是p點)
然後再查p點下面的7個點看和p點的距離有無小於d嗎

所以一般來想用x座標排序應該比較直觀吧

為什麼要特地用y座標排序?有什麼特別的意義嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.105.145.160
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1541325635.A.A68.html
※ 編輯: sooge (120.105.145.169), 11/04/2018 18:12:20
推 FRAXIS: 遞迴是按照 x 座標切的  先依照 y 座標排序
→ FRAXIS: 只是為了避免在遞迴過程中重複計算
→ sooge: 聽不太懂 可以再解釋的詳細一點嗎><   重複計算是什麼意思
→ sooge:  遞迴和取list K是不同步驟不是嗎
推 FRAXIS: 因為每次 recursion call 都要用 y 值的順序來掃描
→ FRAXIS: 而且遞迴會被呼叫很多次  所以一開始就先按照 y 軸排序
→ FRAXIS: 每次遞迴呼叫的時候就按照這順序掃描就好了 不用重排
→ sooge: 很像懂其中的意思了 謝謝你