http://www.codechef.com/FEB11/
On Thu, Feb 3, 2011 at 12:54 AM, Dave <dave_and_da...@juno.com> wrote: > What contest? > > On Feb 2, 12:41 pm, radha krishnan <radhakrishnance...@gmail.com> > wrote: > > 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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 algogeeks@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. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
