[問題] 求N點最短距離
這題目是說
在座標上有N個點
求出最短的兩個點的座標
如果有多對一樣最短
就顯示所有最短的座標對
我的想法大致上是
1.先將N個點依序當作圓心
從1為半徑開始創出
圓的方程式
如(4,3)->(X-4)^2+(Y-3)^2 = 1
2.把其他點帶入該方程式
若沒有點落在該圓上或是圓內
便逐漸擴大圓之半徑(每次+1)
直到有點滿足以上條件
3.紀錄滿足其條件的點的座標
以及當時圓的半徑
4.換到下一個點 一樣創方程式
不同的是 半徑從前一次紀錄的長度開始察找
當都無滿足的點 則換到下個點作1.
當有滿足的點 則每次縮小1/2半徑 直到沒有點滿足為止
當在比前一次紀錄的半徑小或是等於時
就找到有滿足的點 則先前紀錄的半徑更新
而先前滿足的點座標一刪除
5.最後剩下的座標在互相比較即得最短距離
問題1:代入方程式的次數大約為N*(N-1) 時間複雜度相當高
問題2:當各點距離遙遠(如:>=100)第一次做察找也會相當費時
問題3:最後候選的點過多(如每個點距離都小於一)就要比上N*(N-1)/2次
综合以上的問題 我絕這不是個好的演算法
不知道版上有沒有高手可以指點迷津
PS:只講演算法即可
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.230.112.251
推
05/13 23:08, , 1F
05/13 23:08, 1F
→
05/13 23:09, , 2F
05/13 23:09, 2F
→
05/13 23:09, , 3F
05/13 23:09, 3F
推
05/14 08:06, , 4F
05/14 08:06, 4F
→
05/14 08:09, , 5F
05/14 08:09, 5F
推
05/14 09:49, , 6F
05/14 09:49, 6F
推
05/14 11:46, , 7F
05/14 11:46, 7F
推
05/14 11:59, , 8F
05/14 11:59, 8F
→
05/14 12:00, , 9F
05/14 12:00, 9F
推
05/14 13:56, , 10F
05/14 13:56, 10F
推
05/14 15:37, , 11F
05/14 15:37, 11F
→
05/14 16:00, , 12F
05/14 16:00, 12F
→
05/14 18:38, , 13F
05/14 18:38, 13F
推
05/14 21:53, , 14F
05/14 21:53, 14F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
