Поиск трех точек, ближайших к каждой точке в 2D-плоскости

Вам дан список точек на плоскости, напишите программу, которая выводит каждую точку вместе с тремя другими ближайшими точками к нему. Эти три точки отсортированы по расстоянию.

Например, для данного набора точек каждая строка имеет форму: ID x-координата y-координата

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  

Ваша программа должна вывести:

1 2,3,4   
2 1,3,4   
3 1,2,4   
4 1,2,3   
5 4,3,1  

Это вопрос интервью, который я нашел на онлайн-форуме. Я могу придумать решение O (n * n): вычислить расстояние от каждой точки до каждой другой точки. Вернуть минимальное расстояние точек для этой точки. Повторите процесс для других точек