|
0
Ненавижу 1С
гуру
10.08.12
✎
10:22
|
Есть массив структур с тремя полями X,Y - координаты центра, R - радиус окружности
Требуется найти пару пересекающихся окружностей в массиве (любую) или убедиться, что их нет
Есть возможность поиска быстрее чем O(n^2)?
|
|
|
4
zva
10.08.12
✎
12:35
|
Думаю, есть...
Сначала упорядочиваем окружности по коордтнате х за О(N*ln(N))
Потом алгоритм сканирующей линии (вертикальной), аналогичный для поиска пересечения отрезков. Он тоже, вроде, за О(N*ln(N)) должен работать
|
|
