Поиск массива точек в определенном радиусе
Уфф, давно я не был на DTF. Появился у меня тут вопрос.
В общем задача такая, есть массив точек (x, y), далее мне нужно получить массив точек который лежит в пределах определенного радиуса(расстояния) с определенным центром. Изначальный массив может быть довольно большим, по этому обычный перебор массива и проверка расстояния от точки до точки не по…
Чет я не очень понял, каким образом проход по массиву с проверкой элементарного условия (O(n)) может не подходить из-за медлительности. Но при этом ты хочешь строить k-d дерево, сложность чего больше.
Элементарное условие? Для двумерного случая для каждой точки по 2 сложения и возведение в квадрат и ещё 1 сложение после этого. Я чертила по образованию, могу хуйню нести, но разве это не O(n**2)?
А как выше написали, кд — н*лог(н)