如果點不能排序
那麼基本上就是所有點輸入一遍就要有結果出來
這邊我有一個想法
利用類似hash或是bucket sort的作法來完成
把原點往外分為k份扇形區域
alpha角度除以扇形取floor則為c
當一個點被輸入時
會決定落在哪個扇形區域
然後前後c個counter會+1
更新目前最大的counter是誰
所有點都輸入之後
看最後紀錄的最大counter決定是哪個方位即可
演算法複雜度O(nc)
c為常數所以視為O(n)
這個方法有個問題
扇形的切割是不連續的區域
所以取得的方位依然不準
如果無限制切割則會導致c值很大
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.90.212
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1405269769.A.534.html
※ 編輯: iamstudent (218.161.90.212), 07/14/2014 00:44:28