设d[i][j] = distances between points i and 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] = list of all points (p, q) that have d[p][q] = x .
现在，对于每一对点(i, j)，count(i, j)必须迭代H[ d[i][j] ]，并计算该列表中与点i和j形成正方形的点。
这在实践中应该运行得非常快，我不认为它会比O(n^3)更糟糕（我甚至不确定它会变得那么糟糕）。

这个问题可以用O(n)空间在O(n^1.5)时间内解决。
基本思想是按X或Y坐标对点进行分组，注意避免分组过大。详情请参阅Finding squares and rectangles in sets of points文件。本文还涵盖了许多其他情况（允许旋转正方形，允许矩形，并在更高的维度工作）。
我在下面解释了他们的二维轴对齐的正方形查找算法。请注意，我将它们的树集更改为散列集，这就是为什么我给出的时间界限不是O(n^1.5 log(n))：
1.把所有的点做一个散列集。您可以使用它来快速检查点是否存在。
1.按点的X坐标对点进行分组。将任何具有超过sqrt(n)个点的组断开，并按其Y坐标重新分组那些现在空闲的点。这保证了组最多有sqrt(n)个点 ， 保证了每个正方形都有一个组有两个正方形的角点。
1.对于每个群g，对于g中的每对点p,q，检查包含p和q的两个可能正方形的其他两个点是否存在。记录你找到了多少。注意重复的点（两个相对的点是否也在一个组中？）.
为什么会这样？唯一棘手的是重组。如果一个正方形的左列或右列所在的组不是太大，那么当迭代该列组时，将找到该正方形。否则 * 它的左上角和右上角都被重新分组，放入同一个行组，当该行组被迭代时，将找到该正方形。

时间复杂度为O（N^2），空间复杂度为O（N）：
假设给定的点是一个对象Point的数组，每个Point都有x，y。
1.首先遍历数组并将每个元素添加到HashSet中：这个动作消除了重复，给予我们一个O（1）的访问时间。整个过程的时间复杂度为O（N）
1.使用数学，假设顶点A，B，C，D可以形成一个正方形，AC是已知的，并且它是对角线，那么对应的B，D是唯一的。我们可以写一个函数来计算它。这个过程是O（1）时间的
1.现在让我们回到我们的事情。写一个for-i-loop和一个for-j-inner-loop假设input[i]和input[j]形成一条对角线，在集合中是否找到它的反对角线：如果存在，计数器++;时间复杂度为O（N^2）
我的C#代码：

public int SquareCount(Point[] input)
    {
        int count = 0;

        HashSet<Point> set = new HashSet<Point>();
        foreach (var point in input)
            set.Add(point);

        for (int i = 0; i < input.Length; i++)
        {
            for (int j = 0; j < input.Length; j++)
            {
                if (i == j)
                    continue;
                //For each Point i, Point j, check if b&d exist in set.
                Point[] DiagVertex = GetRestPints(input[i], input[j]);
                if (set.Contains(DiagVertex[0]) && set.Contains(DiagVertex[1]))
                {
                    count++;
                }
            }
        }
        return count;

    }

    public Point[] GetRestPints(Point a, Point c)
    {
        Point[] res = new Point[2];

        int midX = (a.x + c.y) / 2;
        int midY = (a.y + c.y) / 2;

        int Ax = a.x - midX;
        int Ay = a.y - midY;
        int bX = midX - Ay;
        int bY = midY + Ax;
        Point b = new Point(bX,bY);

        int cX =  (c.x - midX);
        int cY =  (c.y - midY);
        int dX = midX - cY;
        int dY = midY + cX;
        Point d = new Point(dX,dY);

        res[0] = b;
        res[1] = d;
        return res;
    }

时间复杂度为O（n^3）一个简单的算法可能是这样的：

for each pair of points
    for each of 3 possible squares which might be formed from these two points
        test remaining points to see if they coincide with the other two vertices

Runtime: O(nlog(n)^2), Space: θ(n), where n is the number of points.

For each point p
Add it to the existing arrays sorted in the x and y-axis respectively.
  For every pair of points that collide with p in the x and y-axis respectively
   If there exists another point on the opposite side of p, increment square count by one.

直觉是计算一个新点创建了多少个正方形。所有方格都是在创建其第四个点时创建的。一个新的点创建一个新的正方形，如果它有任何碰撞点在有关的轴上，并存在“第四”点的对面，完成广场。这就穷尽了所有可能的不同方格。
插入到数组中可以是二进制的，并且检查相对点可以通过访问散列表来完成，该散列表散列了点的坐标。
该算法对于稀疏点是最佳的，因为将存在非常少的要检查的碰撞点。这是悲观的密集广场点的原因相反的最佳。
如果轴阵列中的点在互补轴中具有碰撞，则可以通过跟踪来进一步优化该算法。

首先，观察到每个正方形都可以用它的中心和对应于其中一条对角线的向量来唯一地标识。此外，另一对角线可以通过找到与第一对角线长度相同的正交向量来容易地找到，对于向量（a，b），该正交向量将是（-b，a）。现在，对于每对点，我们将编码唯一的正方形，该正方形可以通过将它们视为对角线，通过其中点的坐标对和向量的方向来形成。
初始化一个存储两对int的multiset，我们称之为 M。同时初始化整型变量 count，值为0。
现在迭代所有的点对（通过点列表上的两次嵌套循环）：
1.假设当前点对为 p1：（x1，y1） 和 p2：然后交换 （p1，p2），如果 x1< x2。
1.将下面的一对int对插入到多集 M - （（x1+x2，y1+y2），（x1-x2，y1-y2）） 中。第一对表示中点（实际上是2 中点坐标），第二对表示与对角线相对应的矢量。
1.如果 y1 > y2，交换 （p1，p2）。查询以下计数，以 M 为单位：* （（x1+x2，y1+y2），（abs（y1-y2），x1-x2））*。将变量 count 增加此查询的答案。
最后返回 count 并返回答案。
时间复杂度：使用多组T.C.时间复杂度为O（n）。时间复杂度为O（n^2）$。
注：执行上述交换是为了保存具有特定方向的对角线向量，此处的方向被认为使得向量的x坐标始终为正。

只是一个想法：如果一个顶点A是一个正方形的一个角，那么在其他角上一定有顶点B，C，D，AB = AD和AC = sqrt（2）AB和AC必须平分BD。假设每个顶点都有唯一的坐标，我想你可以用一个哈希表在O（n^2）内解决这个问题。

这只是Java中的一个示例实现-欢迎任何评论。

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class SweepingLine {

    public static void main(String[] args) {
        Point[] points = {
            new Point(1,1),
            new Point(1,4),
            new Point(4,1),
            new Point(4,4),
            new Point(7,1),
            new Point(7,4)
        };
        int max = Arrays.stream(points).mapToInt(p -> p.x).max().orElseThrow(NoSuchElementException::new);
        int count = countSquares(points, max);
        System.out.println(String.format("Found %d squares in %d x %d plane", count, max, max));
    }

    private static int countSquares(Point[] points, int max) {
        int count = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int x=0; x<max; x++) {
            for (int y=0; y<max; y++) {
                for(Point p: points) {
                    if (p.x == x && p.y == y) {
                        List<Integer> ys = map.computeIfAbsent(x, _u -> new ArrayList<Integer>());
                        ys.add(y);
                        Integer ley = null;
                        for (Integer ey: ys) {
                            if (ley != null) {
                                int d = ey - ley;
                                for (Point p2: points) {
                                    if (x + d == p2.x && p2.y == ey){
                                        count++;
                                    }
                                }
                            }
                            ley = ey;
                        }
                    }
                }
            }
        }
        return count;
    }

    private static class Point {
        public final int x;
        public final int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

这里是一个完整的实现找到对角线点在C++！

• 给定点a和c，返回B和d，它们位于对角上
• 如果B或d不是整数点，则对它们进行dicard（可选）
• 要查找由n个点生成的所有正方形，可以查看此C++ implementation
• 想法归功于Kevman。希望可以帮到你！

vector<vector<int>> createDiag(vector<int>& a, vector<int>& c){
    double midX = (a[0] + c[0])/2.0;
    double midY = (a[1] + c[1])/2.0;
    
    double bx = midX - (a[1] - midY);
    double by = midY + (a[0] - midX);
    double dx = midX - (c[1] - midY);
    double dy = midY + (c[0] - midX);
    
    // discard the non-integer points
    double intpart;
    if(modf(bx, &intpart) != 0 or modf(by, &intpart) != 0 or modf(dx, &intpart) != 0 or modf(dy, &intpart) != 0){
        return {{}};
    }
    return {{(int)bx, (int)by}, {(int)dx, (int)dy}};
}