Это что-то из олимпиадного ? Разовые сдвиги между "кадрами" не очень большие ? Резко прыгать никто не будет между соседними моментами времени ?
Как видно из рисунка, зелёным помечены круги игроков, расстояние между которыми до 2R, где R -- радиус взаимодействия, одинаковый для всех.
Расстояния будут попарно считаться как суммы квадратов разностей dx*dx + dy*dy.
Можно для начала рассматривать для каждого игрока только товарищей, у которых дельты по осям обе не больше 4хR.
Их тогда в среднем будет сильно меньше 1000.
Были на 4хR, за "секунду" сблизились каждый на R, и уже "на связи" ! ;)
Хранить и пересчитывать ближайших с надо запасом, чтобы при небольших сдвигах одного не сравнивать его расстояния со всеми остальными, а только если он сдвинется на R и более.
Надо иметь массив А[1000,999] с парами {№ соседа, расстояние}, максимальным (вдруг они таки "столпятся" и захотят "пообщаться", и тогда пойдут тормоза, выбрать ближайших будет сильно дольше).
Ещё массив Л[1000] с текущим количеством "соседей" для каждого А[i].
И, конечно, позиции Х/У для всех О[1000], где был последний полный пересчёт А[i].
В первый раз пересчитать все расстояния, каждому в А[i] писать только "недалёких", до 16хRхR.
Потом -- сортировка всего А[i], и первые ближайшие до 4хRхR окажутся достойными для общения.
После каждого сдвига игрока И[i] его список пересчитывается целиком, если дельта с О[i] больше RхR (и О[i] обновляется).
В обратном случае -- просто пересчёт дистанций/сортировка внутри прежнего списка А[i] на длину Л[i].
Новый список с дистанциями до 4хRхR надо сравнить со старым, и если кто-то там новый появился, то его пометить для перестройки позже.
И кто "пропал с дистанции" -- тоже требует перестройки.
Полной или не очень, просто добавить/удалить себя к нему -- надо ещё додумать.
Инкрементальные действия между "степами" будут пропорциональны количеству немного шевельнувшихся между "степами" игроков И[i], и в основном на длину списков их "соседей", этого достаточно ?
Простой
Средний
Средний
