@Rahul and Asquare: The algorithm could look like this: 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) when you find a string of duplicates longer than lmax, imax = i lmax = length of string smax = the common slope end scan // O(n) end for i // O(n*(n+ n log n + n) = O(n^2 log n) // Now you know the point imax at which you found the longest string of duplicate slopes, and the value of that duplicated slope j = 1 col_pts(j) = imax // array of collinear points for i = 1 to n with i not_equal imax slope = slope of line through imax and i if ( slope equals smax ) then j = j + 1 col_pts(j) = i end if end for // O(n)
Thus, the entire algorithm is O(n^2 log n) Dave On Oct 15, 2:16 am, rahul patil <rahul.deshmukhpa...@gmail.com> wrote: > On Thu, Oct 14, 2010 at 10:00 PM, Mridul Malpani > <malpanimri...@gmail.com>wrote: > > > by forming n*n pairs of points. now you have to select any 2 pair such > > that these 2 set have atleast 1 points in common, and their slope must > > be equal. > > > this will take O(n^4). > > correct me, if i m wrong. > > I think Dave is correct, > > let us consider there are n points, > n slopes are stored in an array like this > > (1,1) (1,2) (1,3) (1,4) (1,5) ..... (1,n) > (2,2) (2,3) (2,4) (2,5) ..... (2,n) > (3,3) (3,4) (3,5) ..... (3,n) > (4,4) (4,5) ..... (4,n) > > so this will take nlogn time > for n rows > > 1> > for one row it will take logn time( having n elements) > sort this row again nlogn time. > and then in single traverse you will get all the colinear points > in one row(having one point in common) > > nlogn [for sort] * logn [for one row slope calculation] + n > = nlogn [for sort] * logn [for one row slope calculation] > = n(logn )^2 > > for n rows u will have n* n(logn )^2 = n^2 (logn )^2 > > correct me if i am wrong > > > > > > > > > On Oct 14, 7:00 am, Dave <dave_and_da...@juno.com> wrote: > > > @Asquare. Yes, you are wrong. If the slope of the line AB equals the > > > slope of the line AC, then points A, B, and C are collinear. One way > > > to look at it is that because AB and AC have the same slope, they are > > > parallel (if you can call coincident lines parallel), and they both > > > contain point A. Therefore, they are coincident. > > > > Dave > > > > On Oct 13, 3:04 pm, Asquare <anshika.sp...@gmail.com> wrote: > > > > > @Dave - > > > > > Although what u have posed is correct to an extent but this will also > > > > include cases where the line joining the points are parallel and not > > > > collinear > > > > So we will have to impose a check for one of the points involved > > > > in every two same slopes to be coincident. > > > > > Do correct me if i am wrong.. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards, > Rahul Patil- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.