Привет. Заметил в игре Warpips интересную механику когда артиллерия бьёт

в скопление врагов. Хочу повторить это. Может кто подкинуть идею как это реализовать? (как выбрать максимально большую группу точек на плоскости, описываемую окружностью заданного диаметра, найти центр этой окружности)

а я бы сделал так, кинул бы по радиусу, и расширял бы пока например в нем не наберется 200 юнитов условно, при их наборе, делали бы свой круг на 4 части, и в которой из частей больше юнитов, его бы брал в фокус и вот тебе пожалуйста

а если по центру получится? ну т.е. круг должен быть на пересечении этих 4х частей?

Какая асимптотика решения задачи желаемая? Известно, что решение твоей задачи это описанная вокруг некоторого треугольника из трёх точек окружность. Соответственно тебе стоит выбрать такую, которая имеет меньший радиус чем ты задал и включает максимальное число точек. За n^4 это точно решается.

вот

Да, не нужно. Это промежуточный шаг алгоритма. Так вы найдете центр, далее подставите нужный радиус.

А, я понял. Но тогда нужно знать в каждой ноде все остальные что ближе радиуса, а не использовать только ближайшие две?

Да нужно перебирать все точки. Еще раз: вам нужно перебрать центры всех описанных оркужностей - их n^3, для каждой найти число точек попадающих в нее, и за n и выбрать лучшую. Поймите, что для заданного радиуса решение не единственно в общем случае. Эту задачу можно точно решать эффективнее, для этого стоит ознакомиться с вот этой задачей - https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%BA%D1%80%D1%83%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8. Это другая задача, но предложенные решения этой задачи можно обобщить и на вашу.

Мне кажется, что решение с нодами неточное, насколько я его понял. Про два скопления точек - это кажется уже другая задача).

Ну если нодами не правильно, а ваш вариант сработает то мне бы понять как его сделать