c - 在给定 n 个点的平面中找到正方形

Question

给定一个平面上的 n 个点，可以组成多少个正方形...？？

我尝试通过计算每 2 个点之间的距离，然后对它们进行排序，并在验证点和斜率后寻找具有四个或更多个相等距离的点中的正方形。

但这看起来是一种非常复杂的方法。任何其他想法...？？

我认为用于检查等距离线段的动态规划可能会起作用......但无法完全正确地理解......

有更好的主意吗？？？

P.S:方 block 可以是任何方式。它们可以重叠，有共同的一面，一个正方形在另一个正方形内......

如果可能，请提供示例代码来执行上述...

Answer 1

令 d[i][j] = i 和 j 点之间的距离。我们对函数 count(i, j) 感兴趣，它会尽快返回我们可以使用点 i 和 绘制的正方形数量j。

基本上，count(i, j) 必须找到两个点 x 和 y 使得 d[i] [j] = d[x][y] 并检查这 4 个点是否真的定义了一个正方形。

您可以使用 hash table平均在 O(n^2) 中解决问题。设 H[x] = 具有 d[p][q] = x 的所有点 (p, q) 的列表。

现在，对于每对点 (i, j)，count(i, j) 将不得不迭代 H[ d[i][ j] ] 并计算该列表中与点 i 和 j 形成正方形的点数。

这在实践中应该运行得非常快，而且我认为它不会比 O(n^3) 更糟(我什至不确定它是否会变得那么糟糕) .