作者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