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.

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

Approach:

First Have all the points in an array and sort them according to their X axis, which would give:

3 -12.2 12.2 

1 0.0 0.0 

2 10.1 -10.1 

4 38.3 38.3 

5 79.99 179.99 

Then for every point P, calculate the distance from 3 points in the front and 3 point in the back:

For Ex: Point with Id=3 (-12.2, 12.2) does not have 3 points in the back.

Always store only min 3 distances and the corresponding point Ids - Max heap can help here.

Then Sort the points according to their Y Axis, which would give:

2 10.1 -10.1 

1 0.0 0.0 

3 -12.2 12.2 

4 38.3 38.3 

5 79.99 179.99 

Again calculate for every point p, distances from 3 points in the front and 3 points in the back - Always maintaining the Max heap of size 3.

Total complexity: 2nlogn + 4kn + klogk = O(nlogn)

k = 3 here.