[問題] 請問一下 平面很多點(X Y座標) 求最遠兩點 距離

看板Prob_Solve (計算數學 Problem Solving)作者 (旺來)時間14年前 (2010/08/03 20:01), 編輯推噓4(405)
留言9則, 4人參與, 最新討論串1/1
請問存了很多在平面上的很多點座標值的陣列 有什麼方法來求出最遠兩點的距離會比較簡單寫出程式碼 複雜度又不會太高 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.147.141.118

08/03 20:07, , 1F
凸包 + 旋轉卡殼 O(nlgn + n)
08/03 20:07, 1F

08/03 20:08, , 2F
不然就凸包 + 枚舉凸包上的點 O(nlgn + n^2)
08/03 20:08, 2F

08/03 20:08, , 3F
凸包可做常數優化
08/03 20:08, 3F

08/03 20:45, , 4F
咦?原po好久不見~~
08/03 20:45, 4F

08/03 20:50, , 5F
多久了....十年嗎?
08/03 20:50, 5F

08/03 20:50, , 6F
妳還記得真神奇
08/03 20:50, 6F

08/03 23:02, , 7F
第二個做法別亂用,會中招XD
08/03 23:02, 7F

08/04 23:16, , 8F
給的點集本身就是個凸包嗎XD
08/04 23:16, 8F

08/04 23:17, , 9F
沒辦法,原PO說要比較簡單寫出來的 只給丟個好理解的sol2
08/04 23:17, 9F
文章代碼(AID): #1CM0KQ7X (Prob_Solve)
文章代碼(AID): #1CM0KQ7X (Prob_Solve)