问题理解

我们需要统计给定的一组整点中可以组成的正方形的数量。每个正方形由四个不同的点组成，且这四个点必须是正方形的四个顶点。正方形的边可以与坐标轴平行或对角线方向。

解决思路

正方形的性质： 正方形的四个顶点满足一定的几何关系。对于边与坐标轴平行的正方形，四个点的坐标可以表示为 (x, y), (x + a, y), (x, y + a), (x + a, y + a)。 对于对角线方向的正方形，四个点的坐标可以表示为 (x, y), (x + a, y + a), (x - a, y + a), (x, y + 2a) 等形式。 暴力枚举优化： 直接枚举所有四个点的组合会非常耗时（O(n^4)），因此需要优化。 对于每对点 (p1, p2)，计算它们作为正方形的对角线或边时的其他两个点的坐标，并检查这些点是否存在。 使用哈希表来快速查找点是否存在。 哈希表实现： 使用哈希表存储所有点，以便快速查找。 哈希函数设计为 calHash(x, y) = ((x << 7) ^ y) & 262143，使用开放寻址法解决冲突。 避免重复计数： 通过检查点对的顺序和正方形的对称性，避免重复计数。

代码实现

以下是基于上述思路的C++代码实现：

#include <cstdio>
#include <cstring>
 
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
 
int x[1001], y[1001];
int savex[262144], savey[262144];
bool hash[262144];
 
inline int calHash(int x, int y) {
    return ((x << 7) ^ y) & 262143;
}
 
void insert(int x, int y) {
    int h = calHash(x, y);
    int add = prime[(x ^ y) & 7];
    while (hash[h] && (savex[h] != x || savey[h] != y)) {
        h += add;
        h &= 262143;
    }
    hash[h] = true;
    savex[h] = x;
    savey[h] = y;
}
 
bool find(int x, int y) {
    int h = calHash(x, y);
    int add = prime[(x ^ y) & 7];
    while (hash[h] && (savex[h] != x || savey[h] != y)) {
        h += add;
        h &= 262143;
    }
    if (hash[h] && savex[h] == x && savey[h] == y)
        return true;
    return false;
}
 
bool calK(int a, int b) {
    if (x[a] == x[b])
        return false;
    if (y[a] == y[b])
        return true;
    if (((x[a] - x[b]) & (1 << 31)) == ((y[a] - y[b]) & (1 << 31)))
        return true;
    return false;
}
 
inline int Abs(int n) {
    return n < 0 ? -n : n;
}
 
int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        memset(hash, 0, sizeof(hash));
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            insert(x[i], y[i]);
        }
 
        int count = 0;
        for (int i = 0; i < n; i++)
            for (int k = i + 1; k < n; k++) {
                if (calK(i, k)) {
                    int _y = Abs(y[i] - y[k]);
                    int _x = Abs(x[i] - x[k]);
                    if (find(x[i] + _y, y[i] - _x) &&
                        find(x[k] + _y, y[k] - _x))
                        count++;
                }
            }
        printf("%d\n", count);
    }
    return 0;
}

代码解释

哈希表实现： calHash函数计算点的哈希值。 insert函数将点插入哈希表，使用开放寻址法解决冲突。 find函数检查点是否存在于哈希表中。 正方形检查： calK函数判断两点是否可以构成正方形的对角线或边。 对于每对点 (p1, p2)，计算其他两个点的坐标，并检查这些点是否存在于哈希表中。 主函数main： 读取输入数据，直到遇到n=0为止。 调用insert函数将所有点插入哈希表。 遍历所有点对，统计可以组成的正方形的数量，并输出结果。