作者ownlai (旺來)
站內Prob_Solve
標題[問題] 請問一下 平面很多點(X Y座標) 求最遠兩點 距離
時間Tue Aug 3 20:01:27 2010
請問存了很多在平面上的很多點座標值的陣列
有什麼方法來求出最遠兩點的距離會比較簡單寫出程式碼
複雜度又不會太高
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.147.141.118
1F：推 yuscvscv:凸包 + 旋轉卡殼 O(nlgn + n) 08/03 20:07
2F：→ yuscvscv:不然就凸包 + 枚舉凸包上的點 O(nlgn + n^2) 08/03 20:08
3F：→ yuscvscv:凸包可做常數優化 08/03 20:08
4F：推 aecho:咦？原po好久不見~~ 08/03 20:45
5F：→ ownlai:多久了....十年嗎? 08/03 20:50
6F：→ ownlai:妳還記得真神奇 08/03 20:50
7F：推 seanwu:第二個做法別亂用，會中招XD 08/03 23:02
8F：推 yuscvscv:給的點集本身就是個凸包嗎XD 08/04 23:16
9F：→ yuscvscv:沒辦法，原PO說要比較簡單寫出來的 只給丟個好理解的sol2 08/04 23:17