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

看板Grad-ProbAsk作者 (喜歡平井桃)時間7年前 (2018/11/04 18:00), 7年前編輯推噓2(2推 0噓 6→)
留言8則, 2人參與, 7年前最新討論串1/1
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
推
11/05 10:57, 7年前 , 1F
遞迴是按照 x 座標切的 先依照 y 座標排序
11/05 10:57, 1F
→
11/05 10:57, 7年前 , 2F
只是為了避免在遞迴過程中重複計算
11/05 10:57, 2F
→
11/05 13:10, 7年前 , 3F
聽不太懂 可以再解釋的詳細一點嗎>< 重複計算是什麼意思
11/05 13:10, 3F
→
11/05 13:10, 7年前 , 4F
遞迴和取list K是不同步驟不是嗎
11/05 13:10, 4F
推
11/06 11:21, 7年前 , 5F
因為每次 recursion call 都要用 y 值的順序來掃描
11/06 11:21, 5F
→
11/06 11:21, 7年前 , 6F
而且遞迴會被呼叫很多次 所以一開始就先按照 y 軸排序
11/06 11:21, 6F
→
11/06 11:22, 7年前 , 7F
每次遞迴呼叫的時候就按照這順序掃描就好了 不用重排
11/06 11:22, 7F
→
11/07 12:17, 7年前 , 8F
很像懂其中的意思了 謝謝你
11/07 12:17, 8F
‣ 更多 sooge 的文章
文章代碼(AID): #1RtiD3fe (Grad-ProbAsk)