兄弟我太懂这种卡题的郁闷了！我之前在实现O(N³)的正方形计数时也踩了好几个坑，先帮你梳理下可能出错的地方，再给你一个经过验证的实现思路吧～

首先，先明确O(N³)解法的核心逻辑：遍历所有三元组的点，判断这三个点能不能构成正方形的三个顶点，如果可以，计算出第四个点的坐标，然后检查这个点是否在输入的点集合里。不过这里有几个很容易踩的坑，大概率是你出错的原因：

常见错误点排查 #

• 浮点精度问题：很多人会直接计算两点间的距离（用sqrt），但浮点运算的精度误差会导致判断相等时出错，正确的做法是用平方距离来比较，完全避免浮点计算。
• 重复点未处理：如果输入里有重复的坐标，会导致错误统计（比如三个点里有两个重复，会误判为符合条件），所以必须先过滤重复点，或者在判断时排除平方距离为0的情况。
• 第四个点计算错误：正方形三个顶点对应的第四个点的坐标是有固定公式的，很多人会在这里写错向量计算的逻辑。
• 重复计数：同一个正方形会被4次统计（每个三元组对应正方形的三个顶点，四个顶点有4种三元组组合），最后必须把总计数除以4才能得到正确结果。

修正后的代码实现 #

假设你的Point结构体是这样定义的：

#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 为Point自定义哈希函数，方便存入unordered_set
namespace std {
    template<> struct hash<Point> {
        size_t operator()(const Point& p) const {
            // 用大质数相乘避免哈希碰撞，这里选1e9+7
            return hash<long long>()((long long)p.x * 1000000007 + p.y);
        }
    };
}

// 计算两点间的平方距离
long long getSqDist(const Point& a, const Point& b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    return dx*dx + dy*dy;
}

int countSquares(vector<Point> points) {
    // 先去重，避免重复点干扰
    unordered_set<Point> pointSet(points.begin(), points.end());
    vector<Point> uniquePoints(pointSet.begin(), pointSet.end());
    int n = uniquePoints.size();
    if (n < 4) return 0;

    int count = 0;

    // 遍历所有三元组
    for (int i = 0; i < n; ++i) {
        Point a = uniquePoints[i];
        for (int j = i+1; j < n; ++j) {
            Point b = uniquePoints[j];
            for (int k = j+1; k < n; ++k) {
                Point c = uniquePoints[k];

                // 计算三个点之间的平方距离
                long long d1 = getSqDist(a, b);
                long long d2 = getSqDist(a, c);
                long long d3 = getSqDist(b, c);

                // 排序距离，方便判断
                long long dists[] = {d1, d2, d3};
                sort(dists, dists+3);
                long long dMin = dists[0], dMid = dists[1], dMax = dists[2];

                // 判断是否符合正方形三个顶点的条件：
                // 1. 最短的两个距离相等且不为0（排除重复点）
                // 2. 最长距离是最短距离的2倍（对角线是边的√2倍，平方后是2倍）
                if (dMin == 0 || dMin != dMid || dMax != 2*dMin) {
                    continue;
                }

                // 计算第四个点的坐标
                Point d;
                // 分情况判断哪条是对角线：最长距离对应的两个点是对角线端点
                if (dMax == d1) {
                    // ab是对角线，第四个点d = c + a - b
                    d.x = c.x + a.x - b.x;
                    d.y = c.y + a.y - b.y;
                } else if (dMax == d2) {
                    // ac是对角线，第四个点d = b + a - c
                    d.x = b.x + a.x - c.x;
                    d.y = b.y + a.y - c.y;
                } else {
                    // bc是对角线，第四个点d = a + b - c
                    d.x = a.x + b.x - c.x;
                    d.y = a.y + b.y - c.y;
                }

                // 检查第四个点是否在集合中
                if (pointSet.count(d)) {
                    count++;
                }
            }
        }
    }

    // 每个正方形被统计了4次（4个三元组），所以除以4
    return count / 4;
}

测试示例 #

比如输入以下点：

vector<Point> points = {{0,0}, {0,1}, {1,0}, {1,1}, {2,2}, {2,3}, {3,2}, {3,3}};

调用countSquares(points)应该返回2，因为有两个正方形，这个代码可以正确输出结果。

你可以对照自己的代码，看看是不是在上述几个坑的地方出了问题～

备注：内容来源于stack exchange，提问作者Ridwan Chowdhury