@Top Coder: Calculate the slope of the line from an arbitrary point
outside the region to each point in the region. Then find the median
of these slopes. If there are an odd number of given points and if the
line through the arbitrary point outside the region with the median
slope contains an odd number of the given points, or if there are an
even number of given points and if the line with the average slope of
the two middle slopes passes through an even number of given points,
then that line solves the problem. This occurs with probability 1,
i.e., almost all the time. Otherwise, choose another arbitrary point
and repeat the calculation. The complexity is O(n) time and O(n)
space.
Dave
On Dec 31, 7:29 am, top coder <topcode...@gmail.com> 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 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.
