作者sooge (喜欢平井桃)
看板Grad-ProbAsk
标题[理工] 演算法 the closest pair 的问题
时间Sun Nov 4 18:00:31 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1541325635.A.A68.html
※ 编辑: sooge (120.105.145.169), 11/04/2018 18:12:20
1F：推 FRAXIS: 递回是按照 x 座标切的 先依照 y 座标排序 11/05 10:57
2F：→ FRAXIS: 只是为了避免在递回过程中重复计算 11/05 10:57
3F：→ sooge: 听不太懂 可以再解释的详细一点吗>< 重复计算是什麽意思 11/05 13:10
4F：→ sooge: 递回和取list K是不同步骤不是吗 11/05 13:10
5F：推 FRAXIS: 因为每次 recursion call 都要用 y 值的顺序来扫描 11/06 11:21
6F：→ FRAXIS: 而且递回会被呼叫很多次 所以一开始就先按照 y 轴排序 11/06 11:21
7F：→ FRAXIS: 每次递回呼叫的时候就按照这顺序扫描就好了 不用重排 11/06 11:22
8F：→ sooge: 很像懂其中的意思了 谢谢你 11/07 12:17