"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!!
Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc.
Team Cracking The Code
About Me
▼
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
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 .
I think the following algorithm will work:-
ReplyDeleteTake 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 .