半径内的最大坐标数

Question

给定敌人坐标 x 和 y 的列表以及导弹的伤害半径 r，找到引爆炸弹的最佳坐标（cx，cy）以杀死最多数量的敌人。

我的第一直觉是瞄准敌人的质心（所有坐标的平均值），但这似乎是错误的，因为如果敌人聚集在彼此远离的3个营地中，那么质心将不会击中任何人。

有没有多项式时间算法来解决这个问题？这看起来像是一个组合问题。这个问题通常怎么称呼？

Answer 1

如果存在任何可能的爆炸圈包含至少 2 个敌人，则存在一个最佳爆炸圈，其边缘至少有 2 个敌人。

对于每对距离不超过爆炸圈直径的敌人，有两个直径合适的圆圈可以互相接触。

全部测试。