如果一组点n中有三个点是共线的，最好的算法是什么？如果不是微不足道的话，请解释复杂度。
谢谢
巴拉
最佳答案
如果你能想出一个比o（n^2）更好的算法，你可以发布它！
这个问题是3-SUM Hard，是否有次二次算法（即优于o（n^2））是一个开放问题。许多常见的计算几何问题（包括你的问题）已经被证明是3sum困难，这类问题正在增长。与np硬度一样，3sum硬度的概念在证明某些问题的“韧性”时也被证明是有用的。
要证明您的问题是3sum困难的，请参阅此处的优秀Surver论文：http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
您的问题出现在上述文章的第3页（方便地称为3点在线）。
所以，目前最著名的算法是o（n^2），您已经有了它：-）