Quark, если это вы стороны треугольников обрабатываете, то лучше брать не отрезки в 3d координатах, а номера точек. Там же треугольники индексами в массиве точек заданы, верно? Сортировать 2 инта всяко легче чем точки.
mayton2019, ссылку почитайте. Там алгоритмы для нахождения представления чисел, существующего по теореме лагранжа. Но формулировка у автора вопроса кривая, да.
Надо бы понять, как это апи работает. А то, может, задача вообще не решаемая. Если апи отдает до 100 пользовтелей с данной подстрокой, допустим, с минимальными внутренними id, то может быть, что там 100 пользователей со строкой abc, перед самим пользователем abc. И вы никаким запросом этого abc не получите.
mayton2019, Жесть. Интересно, как долго оно решать будет. Там же 2^66 вариантов! Конечно, отсечения какие-то у него будут, но я боюсь это нереально долго будет. А какая-нибудь система символьной алгебры, или тупо метод гауса, дай бог 7^3 шагов сделает.
mayton2019, Если свапать только 2 ключа, то нарушится свойство дерева поиска. Поэтому обычно используют именно повороты. Тут не тоько ключи меняются местами, но и стуктура дерева.
Ну, и конечно, вопрос в скорости этого процесса. Так-то, очевидно, что всегда можно вообще все дерево разобрать на элементы и потом из них собрать новое, идеально сбалансированное дерево.
Yatagarashy, Раз ваш второй вопрос (про структуры) сюда сдублировали, отвечу тут:
Чтобы генерировать структуры, надо сначала сгенерировать ландшафт. Возможно несколько соседних чанков тоже (по размеру структуры). Потом среди них посмотреть, в каких точках структура может теоретически быть (перепад высот, биом и т.д). Потом надо какой-то другой шум взять в качестве случайной величины и с заданной вероятностью решить, в каких точках структуры генерируются. Потом остается только аккуратно их впендюрить.
В качестве случайной величины можно, например, взять какой-то шум. С резкими перепадами высот, чтобы структуры рядом не спавнились. Надо считать, что стурктура ставится там, где этот шум имеет достаточно большое значение (если все условия для возможности спавна выполняются).
Трюк генерации в следующем: научитесь генерировать какбы всю карту целиком, без разбития на чанки. Эта генерация будет в несколько проходов. Сгенерили высоту, биом, разлили воду, растительность, структуры. И вот когда вам надо разбить генерацию на чанки, чтобы сгенерировать вот этот вот чанк на этапе N, вам надо его и все соседние сгенерировать до этапа N-1. Причем эти соседние чанки могут быть за границей видимости и не требовать генерации по всем этапам. Тут надо все лениво генерировать и кешировать.
Чем больше у вас структуры, тем больше чанков надо генерировать вокруг локации.
Quark, Да, ребра придется считать самостоятельно. Но это просто.
У вас же есть список троек, опысывающих треугольники номерами точек? Вот вы привели в пример треугольник {0,1,2}. Точно должны быть треугольники {1, 0, a}, {2, 1, b}, и {0, 2, c} (порядок точек может быть любым). Эти три треугольника - прямые соседи {1,2,0} - ведь они делят с ним стороны. Вам надо найти треугольник с такой же парой точек. Можно было бы тупо пройтись по всему списку треугольников и сравнить стороны, но это медлено. Но подумайте, эта задача практически идентична такой: Дан массив с числами. Каждое число встречается ровно 2 раза. Найдите пары индексов с одинаковыми числами. Только в вашей задаче чисел по три и совпадают они парами.
Понятно, как быстро решать простую задачу. Или отсортировать массив с индексами, или использовать hash_map. Вам надо просто для каждого числа знать, где оно раньше встречалось. Если оно ее не встречалось - запомните его индекс. Если встречалось - то вот вы нашли пару индексов (текущий и запомненый ранее). Для этого можно использовать hash_map.
Вот у вас будет структура: map из пары int в int. По двум номерам точек оно будет выдавать номер треугольника с такой стороной.
Пройдитесь по списку треугольников один раз. Возьмите все 3 стороны. Если в мапе эта пара точек как ключ еще не лежит, то кладите map[{v1, v2}] = triangle_id. Если там уже что-то лежит, то вот оно является соседом текущего треугольника по стороне. Добавьте в списки смежности этих треугольников друг друга. Не забудьте только номера точек перед использованием в качестве ключа отсортировать, а то может в соседнем треугольнике они в другом порядке идут.
Quark, для построения графа и нужны всякие структуры данных. Или мап из пары интов в инт (по стороне треугольника хранить его номер), или список трекгольников для каждой точки.
Вот есть у вас треугольник {0,1,2} - запомнили, что точка 0 связана с первым треугольником. Допустим, десятый треугольник {1, 33, 0}. Он тоже попадет в список для точки 0. А дальше суть в том, что вы не храните граф, но там, где надо посмотреть всех соседей данной вершины графа (ака треугольник), вы смотрите все треугольники, пересекающиеся с текущим по углу. И когда вы будете искать соседей первого треугольника вы из списка точки 0 найдете десятый треугольник.
