Thank you!
By the way, to do the 'sort s(i+1:n)', if I use counting sort, I think it
should be better.
--------------------------------------------------------------------
imax = 0 // location of longest string of duplicate slopes
lmax = 0 // length of longest string of duplicate slopes
smax = undefined // value of slope
for i = 1 to n-1
for j = i+1 to n
s(j) = slope of the line through points i and j
end for j // O(n)
***************** sort s(i+1:n) // O(n log n) *******************
scan s(i+1:n-1) looking for the longest string of duplicates //
O(n)
On Sat, Oct 23, 2010 at 10:32 PM, Dave <[email protected]> wrote:
> I gave an O(n^2 log n) algorithm to find the maximal number of
> collinear points in a set is given in
> http://groups.google.com/group/algogeeks/msg/d329dda12b332dd1.
> A fairly simple modification could answer the question as to whether
> any three points are collinear.
>
> Dave
>
> On Oct 23, 6:31 pm, Meng Yan <[email protected]> wrote:
> > Given n point on the plane, find out whether any 3point on the same line.
> >
> > How to use recursion to solve the problem? Could you help me find the
> > algorithm and give the time complexity?
> >
> > Bests,
> > Claire
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
