algorithm - 给定2D点列表和正方形网格大小，返回最接近最多点的坐标

Question

以下是我在一次采访中总结出的问题陈述：
有一个表示城市的n x n网格，以及k列表
三元组(x, y, w)，其中(x, y)是事件的坐标，
而w是事件的“价值”你也有一个半径
r，表示您能看到的距离。你从看到一个事件中获得快乐，其中h是（1+到事件的欧几里德距离）（占0距离）如果h=w/d大于d，则幸福为0输出一个具有最高累积幸福感的坐标。
我真的不知道如何解决这个问题，除了通过每一个可能的坐标，计算每个点的幸福度，记录最大值。我还考虑了计算点的质心，并找到最接近质心的整数坐标，但这并没有考虑到活动的“价值”。
解决这个问题的最好方法是什么？

Answer 1

（我看不到明显的最佳算法或数据结构；这可能是他们希望听到你的思维过程而不是解决方案的问题之一。）
在两种明显的方法中：
遍历所有位置并测量到所有事件的距离以计算位置的值
迭代所有事件并增加其周围圆圈中位置的价值
后者似乎是最有效率的。你永远不会看到毫无价值的位置，为了分配价值，你只需要计算一个八分之一的圆，然后将其镜像到圆的其余部分。
很明显，你需要内存空间来存储一个矩形网格的位置值，所以这是一个考虑因素。如果你事先不知道城市的大小，你就必须迭代输入一次来选择网格大小。（相比之下，第一种方法几乎不需要内存空间）。
明智的时间复杂性，你会迭代K事件，而对于每一个，你必须计算与R2相关的许多位置的价值。在迭代事件时，可以保持最大值，因此查找最大值不会增加时间复杂度。（在第一种方法中，您显然需要计算所有相同的w/（d+1）值，而不需要镜像一个圆的八分之一，再加上至少所有其他无用位置的距离。）
如果与城市规模相比，事件数量和周围受影响区域较小，则第二种方法的优势显而易见如果有大量事件和/或R很大，则差异可能不显著。
可能会有一些数学技巧来决定首先检查哪些事件，忽略哪些事件，或何时停止，但是您必须知道更多的细节，例如两个事件是否可以在同一位置发生。在价值排序方面，例如，以最有价值的第一个事件来看，可能是一个优势，因为在某个时刻，在当前最大值之外的“热点”之外的事件可以被忽略。但这在很大程度上取决于数据的具体情况。
更新
当将一个事件的值分布在它周围的位置上时，显然不必多次计算距离；例如，如果r=3，则使用1/d权重生成这个7×7网格：

0      0      0      0.250  0      0      0
0      0.261  0.309  0.333  0.309  0.261  0
0      0.309  0.414  0.500  0.414  0.309  0
0.250  0.333  0.500  1.000  0.500  0.333  0.250
0      0.309  0.414  0.500  0.414  0.309  0
0      0.261  0.309  0.333  0.309  0.261  0
0      0      0      0.250  0      0      0

它只包含八个不同的值然后将此作为模板覆盖在事件位置的网格顶部，将事件的值与权重相乘，并将它们添加到每个位置的值中。
更新
我考虑了这样一种可能性，即只有有一个事件的地点才可能是价值最高的地点，没有r的限制，这是真的这将使问题大不相同但是，很容易创建反例；例如，考虑以下事件：

-      -      60     -      -
-      -      -      -      -
60     -      -      -      60
-      -      -      -      -
-      -      60     -      -

如果限制R大于4，它们将在其周围的位置创造这种价值：

61.92  73.28  103.3  73.28  61.92
73.28  78.54  82.08  78.54  73.28
103.3  82.08  80.00  82.08  103.3
73.28  78.54  82.08  78.54  73.28
61.92  73.28  103.3  73.28  61.92

价值最高的地点为103.3个但是，如果我们设置r=2的极限，我们得到：

40     30     60     30     40
30     49.7   30     49.7   30
60     30     80     30     60
30     49.7   30     49.7   30
40     30     60     30     40

而中间没有位置的位置现在是最大值80的位置。
这意味着必须考虑没有事件的位置，至少是在事件簇周围的凸包内的位置。当然，如果发现两个事件簇之间的距离超过2×r，则可以将它们视为单独的区域在这种情况下，您不必为整个城市创建网格，而是在每个集群周围分离较小的网格。
因此，总体做法是：
使用权重创建大小为2×r的正方形网格。
将事件分成两个距离大于2×r的簇。
对于每个事件集群，创建适合事件周围的最小矩形网格。
对于每个事件，使用权重网格在矩形网格上分配值。
在增加价值的同时，跟踪最大价值。