@Bhavesh: The problem with using hashing is that the slopes, being real numbers, may not have exact representations as floating point numbers. Thus, slopes that should be identical may differ slightly, making them hash into different locations in the hash table. When sorting and comparing adjacent entries, it is possible to use a small tolerance (epsilon) to recognize slopes that mathematically should be equal.
How will you do that with a hash table? Dave On Feb 2, 12:29 pm, Bhavesh agrawal <[email protected]> wrote: > if we just use hashing to store the different slope values .... > > > > On Wed, Feb 2, 2011 at 7:45 PM, bittu <[email protected]> wrote: > > @above > > > Use Simple Mathematics What is collinear Point...?? what is condition > > of collinearity..?? thats it You have done > > > Three or more points P1, P2, P3, ..., are said to be collinear if they > > lie on a single straight line L similarly for N Points .. > > > Let us start from the Very Basic Mathematical Approach > > > Since any 2 points determine 1 line, take 2 of the points and find the > > equation of the line drawn thru these 2 points. > > Substitute the x and y of the either point into the equation and find > > the y-intercept (b) > > > Then, substitute the x and y of the 3rd point into the equation and > > see if the both sides of the equation are =. > > > (y2-y1) ÷ (x2 - x1) = slope > > > y = slope * x + b > > > Point # 1 = (6, 5)=p1 > > Point # 2 = (10, 25)=p1 > > Point # 3 = (12, 30)=p1 > > Point # 4 = (12, 35)=p1 > > > (y2 - y1) ÷ (x2 - x1) = slope > > (25 - 5) ÷ (10 - 6) = slope > > (20) ÷ (4) = slope > > Slope = 5 > > y = m * x + b > > y = 5 * x + b > > > Substitute the x and y of the point (6, 5) into the equation and find > > the y-intercept (b) > > y = 5 * x + b > > 5 = 5 * 6 + b > > 5 = 30 + b > > b = -25 > > y = 5 * x - 25 > > . > > Check your points > > Point # 1 = (6, 5) > > 5 = 5 * 6 - 25 > > 5 = 30 - 25 OK > > . > > Point # 2 = (10, 25) > > 25 = 5 * 10 - 25 > > 25 = 5 * 10 - 25 OK > > . > > Then, substitute the x and y of the 3rd point into the equation and > > see if the both sides of the equation are > > Point # 3 = (12, 30) > > . > > y = 5 * x - 25 > > 30 = 5 * 12 - 25 > > 30 = 60 - 25 = 35 > > Point # 3 = (12, 30) is not on the line > > . > > . > > Point # 4 = (12, 35) > > 35 = 5 * 12 - 25 > > 35 = 60 - 25 =35 > > Point # 4 = (12, 35) is on the line > > > so we can p1,p2,p4 are Collinear > > > 2nd Appraoch Used by Actual Geeks > > > as we Two points are trivially collinear since two points determine a > > line. > > > Three points x_i=(xi,yi,zi) for i=1, 2, 3 are collinear if the ratios > > of distances satisfy > > > x2-x1:y2-y1:z2-z1=x3-x1:y3-y1:z3-z1 > > > A slightly more notice that the area of a triangle determined by > > three points will be zero iff they are collinear (including the > > degenerate cases of two or all three points being concurrent), i.e., > > > | x1 y1 1 | > > | x2 y2 1 |=0 > > | x3 y3 1 | > > > or, in expanded form, > > x1(y2-y3)+x2(y3-y1)+x3(y1-y2)=0 > > > Still If You Have the Doubt Let Me Know & if Any found that anything > > wrong in this..please write correct & efficient ways to do it. > > > Thanks & Regards > > Shashank ""The best way to escape from a problem is to solve it." > > . > > > . > > > -- > > 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%2Bunsubscribe@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- 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 [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.
