EZ
Ну точнее где-то услышал что есть такая штука
Size: a a a
2020 December 19
EZ
А потом там прочитал
MB
3 ужасных строки кода хуже, чем 5-страничное доказательство
Да там и идея простая
MB
Если есть тяжелый сын, то центроид точно в нем
MB
Если тяжелого сына нет, то центроид в нашем наддереве
MB
Но если мы никогда не спускаемся просто так, то центроид это в точности мы
2020 December 20
N
Подскажите как искать ближайших N соседей в Quard Tree?
P
Nikolay
Подскажите как искать ближайших N соседей в Quard Tree?
Типа среди точек найти N пар между которыми минимальное расстояние?
P
Или N ближайших точек к конкретной?
N
Или N ближайших точек к конкретной?
N ближайших к конкретной точки.
P
Я не эксперт, но я бы взял quadtree/octotree
N
Я не эксперт, но я бы взял quadtree/octotree
Спасибо. Да, конечно q-tree выручит.но вот если уже их взять, то не понятно как там такое искать. Если просто делать range query и каждый раз увеличивать квадрат поиска, то это будет неэффективно. Хочется что-то эффективнее.
P
Nikolay
Спасибо. Да, конечно q-tree выручит.но вот если уже их взять, то не понятно как там такое искать. Если просто делать range query и каждый раз увеличивать квадрат поиска, то это будет неэффективно. Хочется что-то эффективнее.
https://stackoverflow.com/questions/32412107/quadtree-find-neighbor
1. Kunio Aizawa et al. - Constant Time Neighbor Finding in Quadtrees: An Experimental Result
2. Kasturi Varadarajan - All Nearest Neighbours via Quadtrees
3. Robert Yoder, Peter Bloniarz - A Practical Algorithm for Computing Neighbors in Quadtrees, Octrees, and Hyperoctrees
1. Kunio Aizawa et al. - Constant Time Neighbor Finding in Quadtrees: An Experimental Result
2. Kasturi Varadarajan - All Nearest Neighbours via Quadtrees
3. Robert Yoder, Peter Bloniarz - A Practical Algorithm for Computing Neighbors in Quadtrees, Octrees, and Hyperoctrees
mm
Как узнать есть ли в графе такая вершина с которой есть путь через все вершины в графе? Через вершины можно ходить больше одного раза. Например 2 -> 3 -> 1 -> 2 -> 5 -> 4
DP
Как узнать есть ли в графе такая вершина с которой есть путь через все вершины в графе? Через вершины можно ходить больше одного раза. Например 2 -> 3 -> 1 -> 2 -> 5 -> 4
в любом графе который не имеет изолированных кусков будет такой путь
K
Ориентированный
DP
а, тогда сложнее
mm
в любом графе который не имеет изолированных кусков будет такой путь
Может я не правильно объяснил, но не в каждой графе будет такой вершины
DP
1<-2->3
такой граф не имеет пути обхода. хотя он связанный
такой граф не имеет пути обхода. хотя он связанный
AK
Находишь компоненты сильной связности в графе, сжимаешь каждую до вершины, дальше если получился бамбук, то значит вершина есть, и это корень, иначе нет такой