Есть массив структур с тремя полями X,Y - координаты центра, R - радиус окружности
Требуется найти пару пересекающихся окружностей в массиве (любую) или убедиться, что их нет

Есть возможность поиска быстрее чем O(n^2)?

Up

(n(n+1))/2 не?

(2) ну это O(n^2)

Думаю, есть...
Сначала упорядочиваем окружности по коордтнате х за О(N*ln(N))
Потом алгоритм сканирующей линии (вертикальной), аналогичный для поиска пересечения отрезков. Он тоже, вроде, за О(N*ln(N)) должен работать

(4)концентрические разных радиусов как отработает?