发现的平方在给定的平面n个点 [英] Finding the squares in a plane given n points

问题描述

给定n个点的平面内，有多少方块可以形成... ...

Given n points in a plane , how many squares can be formed ...??

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

I tried this by calculating the distances between each 2 points , then sort them , and look for the squares in the points with four or more equal distances after verifying the points and slopes.

不过，这看起来像具有很高的复杂性的方法。任何其他的想法？??

But this looks like an approach with very high complexity . Any other ideas ...??

我想动态规划用于检查相等的距离可能会工作的线段......但不能得到的想法完全正确......

I thought dynamic programming for checking for line segments of equal distances might work ... but could not get the idea quite right ....

什么更好的想法？

P.S：该方块可以以任何方式。他们可以重叠，有一个​​共同的一面，里面一个又一个正方形......

P.S : The squares can be in any manner . They can overlap , have a common side, one square inside another ...

这帮助我理解这个问题更好的AP preciable ......如果可能的话请给一个示例code执行上述...

Any links that help my understanding the problem better are appreciable ... If possible please give a sample code to perform the above...

推荐答案

让 D [I] [J] =点i和j 之间的距离。我们感兴趣的是一个函数数（I，J）的回报，尽可能快地，广场，我们可以用点画出的数量我和Ĵ。

Let d[i][j] = distances between points i and j. We are interested in a function count(i, j) that returns, as fast as possible, the number of squares that we can draw by using points i and j.

基本上，数（I，J）必须找到两个点 X 和是，使得 D [I] [J] = D [X] [Y] ，并检查这4个点确实定义了一个正方形。

Basically, count(i, j) will have to find two points x and y such that d[i][j] = d[x][y] and check if these 4 points really define a square.

您可以使用哈希表要解决的问题在 0 （N ^ 2）的平均水平。让 H [X] =所有点（P，Q），其有d列表[P] [Q] = X 。

You can use a hash table to solve the problem in O(n^2) on average. Let H[x] = list of all points (p, q) that have d[p][q] = x.

现在，每一个点对（I，J），数（I，J）将有遍历 H [D [I] [J] 和计数形成以点方在该列表中的点，我和Ĵ。

Now, for each pair of points (i, j), count(i, j) will have to iterate H[ d[i][j] ] and count the points in that list that form a square with points i and j.

这应该在实践中跑得很快，我不认为它可以永远得到差于为O（n ^ 3）（我甚至不能确定它可以永远得到坏）。

This should run very fast in practice, and I don't think it can ever get worse than O(n^3) (I'm not even sure it can ever get that bad).

这篇关于发现的平方在给定的平面n个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！