С
А если поделить плоскость на квадраты 20*20? (Дальше я ещё не придумал)
получим дерево квадрантов ) диапазон не маленький - от -10^9 до 10^9/
Size: a a a
2021 April 04
EZ
Сергей
получим дерево квадрантов ) диапазон не маленький - от -10^9 до 10^9/
Ну для этого и хеши
EZ
тебе нужна диаграмма Вороного
А как она тут поможет, лучшая точка ж может вообще не быть ближайшей ни к одной точке типа Б
AT
тебе нужна диаграмма Вороного
а, есть ограничение на макс. расстояние
С
тебе нужна диаграмма Вороного
спасибо, посмотрю. Но , блин, ещё раз задача в курсе чуть посложнее чем для ПТУ - до кодефорса даже самого слабого дивизиона курс не дотягивает, вот что останавливает от залезания в дебри (
CD
Сергей
получим дерево квадрантов ) диапазон не маленький - от -10^9 до 10^9/
Зачем дерево?
С
Зачем дерево?
а как еще квадрат размера 2*10^9 по одному измерению я в память затолкаю?
CD
Сергей
а как еще квадрат размера 2*10^9 по одному измерению я в память затолкаю?
не понял вопроса
AT
решить можно так: для каждой точки A и B задаёшь координату вдоль Z-order curve. Это делается "смешиванием" бит координат x и y так, что они чередуются. Сортируешь этот массив — у тебя линеаризованное квадродерево. Внутри ячеек со стороной >= 60 метров уже просто в два цикла проходишься по точкам, попавшим в ячейку.
EZ
Сергей
а как еще квадрат размера 2*10^9 по одному измерению я в память затолкаю?
У тебя максимум 10^6 непустых квадратов
CD
Сергей
а как еще квадрат размера 2*10^9 по одному измерению я в память затолкаю?
сделал unordered_map<pair<int, int>, vector<points>> где первое это { point.x / 20, point.y / 20 }
CD
проверил 9 штук
AT
решить можно так: для каждой точки A и B задаёшь координату вдоль Z-order curve. Это делается "смешиванием" бит координат x и y так, что они чередуются. Сортируешь этот массив — у тебя линеаризованное квадродерево. Внутри ячеек со стороной >= 60 метров уже просто в два цикла проходишься по точкам, попавшим в ячейку.
а нет. Не годится. Нужно соседние просматривать
EZ
сделал unordered_map<pair<int, int>, vector<points>> где первое это { point.x / 20, point.y / 20 }
А если все в одном квадрате
EZ
Например
CD
А если все в одном квадрате
да там наверняка координаты целые и различные
CD
можно два фора вокруг точки, но так запросов к мапе больше
AT
а сильно по времени не проходишь?
EZ
да там наверняка координаты целые и различные
Тогда скучно
С
да там наверняка координаты целые и различные
координаты - целые да. О различных речи нет. а в чем глубинный смысл point.x / 20?? не пойму (