AD
Можно и нужно меньше
Size: a a a
2020 April 02
AD
Хеши, деревья
AD
Вам в помощь
AD
А есть для пересечения прямых и более замороченные алгоритмы
AN
Потому что о от платформ
То есть типа мой цикл фор - гумно, нужны хеш-таблицы?
AD
Цикл фор не будет работать с дофигалиардом платформ
AD
Пространственное хеширование в принципе может ограничивать тебе до отсутствия цикла
AN
Цикл фор не будет работать с дофигалиардом платформ
Будет, но долго.
AN
Это тестовое. Можно оставить как есть, ибо платформ тут 15 штук, а можно выибнуться и задействовать деревья.
AD
Выибунися и задействовать хеши, их проще
AN
А может стоит запомнить номер последней платформы, на которой побывал шар и дальше обходить с неё? Будет оптимальнее как минимум вдвое.
AD
Порезать плоскость на n кусочков, перенумеровать, платформы перекомпоновать так чтобы сидели целиком в куске
AD
Дальше ты считаешь номер кусочка шара
AD
И по хешмапе вытаскиваешь платформы, если хеш поменялся
AD
Так у тебя оно уже О(1).
AN
Порезать плоскость на n кусочков, перенумеровать, платформы перекомпоновать так чтобы сидели целиком в куске
А что такое кусочки? Прямоугольники с границами что ли? И по ним проверять, в каком сейчас шар?
AS
А что такое кусочки? Прямоугольники с границами что ли? И по ним проверять, в каком сейчас шар?
Квадтри
AN
Так у тебя оно уже О(1).
А будет О(1/2)
AN
По моему способу
AN
По твоему - O(log2(N))