Generalizing the problem, let there be n points (x_i, y_i), where x_i and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line separating the points into two sets of equal cardinality can be found as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find the slopes of the lines from the point (X, Y) to each (x_i, y_i). The point (X, Y) is constructed so that each of these slopes will be distinct. Find the median M of these slopes. Then the line
y = M(x - X) + Y will separate the points as desired. It will pass through exactly one of the points if n is odd, and will miss all of the points if n is even. This is O(n) in time and O(n) in space, where n is the number of points. Dave On Jan 21, 11:45 pm, Divya Jain <[email protected]> wrote: > assume the region to be (0,0) , (10,0), (0,10), (10,10) > > On 22 January 2011 08:33, Dave <[email protected]> wrote: > > > > > @Divya: The coordinates of the points are between 0 and 1 and are > > integers. That can't be right. > > > Dave > > > On Jan 21, 1:46 pm, divya <[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;}; > > > > input : struct point * points, int length > > > -- > > 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.
