相关疑难解决方法(0)

问题:

在2维平面上给出N个点.同一条直线上的最大点数是多少？

问题有O(N ²)解决方案:遍历每个点并找到dx / dy与当前点相关的点数.将dx / dy关系存储在哈希映射中以提高效率.

有没有比O(N ²)更好的解决这个问题的方法？

如果任何三个点在一组点中共线,那么找出最佳算法是什么？如果不是微不足道,请解释复杂性.

由于
巴拉

我被问到这个采访问题(C++,algos)并且不知道如何解决它.

给定一个数组说Arr [N]包含N个不同点的笛卡尔坐标,计算三元组的数量(Arr [P],Arr [Q],Arr [R]),使得P <Q <R <N并且得到点Arr [ P],Arr [Q],Arr [R]共线(即位于同一直线上).

有任何想法吗？我可以使用什么算法？