Monday, July 11, 2011
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
Subscribe to:
Post Comments
(
Atom
)
1 comment :
I think the following algorithm will work:-
Take a point (0,0) (Or any other convinient point , it does not matter) .
Let's call it A .
Now , find the slope of all the points in the region with this point A.
Find the median for this slope array formed this way .This line should divide the region into two pieces .
Post a Comment