I wonder U people discuss the solution during the contest ? On Wed, Feb 2, 2011 at 11:59 PM, Bhavesh agrawal <agr.bhav...@gmail.com> wrote: > if we just use hashing to store the different slope values .... > > On Wed, Feb 2, 2011 at 7:45 PM, bittu <shashank7andr...@gmail.com> 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 algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. >
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
