Find the distance between each of the points and the origin(0,0) and sort the points based on this distance. Also, divide the points based on which quadrant they belong. If the difference between their distance(from origin) between 2 points is less and they belong to the same quadrant, then they are likely to be close. So, instead of comparing each point with every other point as in the O(N^2) solution. We can compare a given point only with a subset of points that appear to be close.
On Wed, Dec 21, 2011 at 1:00 AM, SAMMM <[email protected]> wrote: > You are given a list of points in the plane, write a program that > outputs each point along with the three other points that are closest > to it. These three points ordered by distance. > The order is less then O(n^2) . > > For example, given a set of points where each line is of the form: ID > x-coordinate y-coordinate > > > 1 0.0 0.0 > 2 10.1 -10.1 > 3 -12.2 12.2 > 4 38.3 38.3 > 5 79.99 179.99 > > > > Your program should output: > > > 1 2,3,4 > 2 1,3,4 > 3 1,2,4 > 4 1,2,3 > 5 4,3,1 > > -- > 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. > > -- 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.
