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.
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