@ Mridul - even I had the same confusion.. Wht dave says is not this.. He is considering one point at a time (say A) and checking the maximum number of points (say n) which have the same slope with A...
now wen he considers the next point (say B) and calculates slope with B for all other points the maximum number of points that have same slope must be greater than n in order to be considered over the previous case.. and so on So in any case since one point is common (A or B or whtever).. so all will be collinear... so we need not find the atleast one common pnt..(as stated by u) @Dave - Hopefully wht i hv understood frm ur logic is correct now.. But I still have a doubt in the complexity.. coz each point will consider other (n-1) points so n^2 there and then sorting for each point can not be log n.. it shd be n log n. therefore the complexity would be O(n^3log n) which is not as low as required.. @Gene - Could u plz explain hw u arrived at these two conditions sqrt(A^2 + B^2) = 1 and either A>0 or (A=0 and B = 1)...?? And wht do u mean by "equivalence classes of points"..?? Is it equal values of A and B?? -- 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.
