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