Pick a random point (x0,y0) in the plane that is not equal to any of the given points (x_i,y_i). For each i, calculate the slope m_i of the line that passes through (x0,y0) and (x_i,y_i). Find the median M of the slopes. If there are two or more slopes equal to M, start over with a new random (x0,y0). The line through (x0,y0) with slope M separates the given points in the desired way.
Dave On Aug 12, 6:12 am, amit <[email protected]> wrote: > Within a 2D space, there is a batch of points(no duplicate) in the > region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide > the region to 2 parts with half points in each .the input will be an > array of points and the length of the array. > struct point{ > int x; > int y; > > > > };- 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.
