n^2lgn复杂度寻找n点3点共线问题

如题,n个平面点,存在n^2lgn复杂度的算法,找出是否存在3点共线现象。

Show how to determine in O(n^2
lgn)time whether any three points in a set of n
points are colinear.

作者: iamabad   发布时间: 2011-06-14

对每一个点,算出到其他点的斜率,排个序或者Hash,都可以,排序的话n^2*log(n),Hash的话n^2

作者: litaoye   发布时间: 2011-06-14