如何高效计算笛卡尔坐标系点集中的等边与等腰三角形数量？

核心优化思路 #

你的现有代码采用三重循环（O(n³)时间复杂度），即便加了哈希表也无法本质提升效率。更优的思路是以每个点为顶点，统计距离频次，将时间复杂度降到O(n²)，同时利用整数坐标的特性简化等边三角形的判断。

关键结论：整数坐标下无有效等边三角形 #

非退化的等边三角形无法由三个整数坐标点构成——因为等边三角形的高为(√3/2)×边长，边长平方为整数时，高的平方是分数，而整数坐标两点的距离平方必为整数，矛盾。因此若输入全为整数坐标，等边三角形数量直接返回0即可。

等腰三角形计数的高效步骤 #

1. 统计每个点为顶点的潜在等腰三角形：
   • 对每个点P，遍历其余所有点，计算到P的距离平方，用哈希表统计每个距离的出现次数。
   • 若某距离d出现k次，则可组成k*(k-1)/2个以P为顶点的等腰三角形（从k个点中选2个与P配对）。
2. 剔除退化三角形（三点共线）：
   • 三点共线的“等腰”结构并非有效三角形，需要扣除。对每个点P，统计同一直线上的点的数量：
     • 计算点Q相对于P的向量(dx, dy)，将其标准化（除以dx、dy的最大公约数，且保证第一个非零分量为正，确保同一直线的向量归一化后相同）。
     • 若某标准化向量对应k个点，则需扣除k*(k-1)/2个退化结构。
3. 最终计数：总潜在等腰数减去退化数，即为有效等腰三角形数量。

优化后的C代码实现 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// 哈希表节点，用于统计距离频次
typedef struct DistFreqNode {
    long long distSq;
    int count;
    struct DistFreqNode* next;
} DistFreqNode;

// 哈希表节点，用于统计方向频次（处理共线情况）
typedef struct DirFreqNode {
    int dx;
    int dy;
    int count;
    struct DirFreqNode* next;
} DirFreqNode;

// 计算最大公约数
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 标准化向量：除以gcd，确保第一个非零数为正
void normalizeVector(int* dx, int* dy) {
    int g = gcd(*dx, *dy);
    if (g == 0) return; // 同一点，跳过
    *dx /= g;
    *dy /= g;
    // 统一方向：第一个非零分量为正
    if (*dx != 0) {
        if (*dx < 0) {
            *dx = -*dx;
            *dy = -*dy;
        }
    } else {
        if (*dy < 0) {
            *dy = -*dy;
        }
    }
}

// 哈希函数：距离平方的哈希
unsigned int hashDist(long long distSq, unsigned int tableSize) {
    return (unsigned int)(distSq % tableSize);
}

// 哈希函数：方向向量的哈希
unsigned int hashDir(int dx, int dy, unsigned int tableSize) {
    return (unsigned int)((abs(dx) * 31 + abs(dy)) % tableSize);
}

// 插入距离频次哈希表
void insertDist(DistFreqNode** table, long long distSq, unsigned int tableSize) {
    unsigned int idx = hashDist(distSq, tableSize);
    DistFreqNode* node = table[idx];
    while (node != NULL) {
        if (node->distSq == distSq) {
            node->count++;
            return;
        }
        node = node->next;
    }
    // 未找到，创建新节点
    DistFreqNode* newNode = (DistFreqNode*)malloc(sizeof(DistFreqNode));
    if (!newNode) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->distSq = distSq;
    newNode->count = 1;
    newNode->next = table[idx];
    table[idx] = newNode;
}

// 插入方向频次哈希表
void insertDir(DirFreqNode** table, int dx, int dy, unsigned int tableSize) {
    unsigned int idx = hashDir(dx, dy, tableSize);
    DirFreqNode* node = table[idx];
    while (node != NULL) {
        if (node->dx == dx && node->dy == dy) {
            node->count++;
            return;
        }
        node = node->next;
    }
    // 未找到，创建新节点
    DirFreqNode* newNode = (DirFreqNode*)malloc(sizeof(DirFreqNode));
    if (!newNode) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->dx = dx;
    newNode->dy = dy;
    newNode->count = 1;
    newNode->next = table[idx];
    table[idx] = newNode;
}

// 销毁距离哈希表
void destroyDistTable(DistFreqNode** table, unsigned int tableSize) {
    for (unsigned int i = 0; i < tableSize; i++) {
        DistFreqNode* node = table[i];
        while (node != NULL) {
            DistFreqNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(table);
}

// 销毁方向哈希表
void destroyDirTable(DirFreqNode** table, unsigned int tableSize) {
    for (unsigned int i = 0; i < tableSize; i++) {
        DirFreqNode* node = table[i];
        while (node != NULL) {
            DirFreqNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(table);
}

// 统计等腰三角形数量
long long countIsosceles(int N, int points[][2]) {
    long long total = 0;
    long long collinear = 0;
    const unsigned int TABLE_SIZE = 10007; // 质数哈希表大小

    for (int i = 0; i < N; i++) {
        // 初始化距离频次哈希表
        DistFreqNode** distTable = (DistFreqNode**)calloc(TABLE_SIZE, sizeof(DistFreqNode*));
        if (!distTable) {
            fprintf(stderr, "内存分配失败\n");
            exit(EXIT_FAILURE);
        }
        // 初始化方向频次哈希表
        DirFreqNode** dirTable = (DirFreqNode**)calloc(TABLE_SIZE, sizeof(DirFreqNode*));
        if (!dirTable) {
            fprintf(stderr, "内存分配失败\n");
            exit(EXIT_FAILURE);
        }

        int px = points[i][0];
        int py = points[i][1];
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            int dx = points[j][0] - px;
            int dy = points[j][1] - py;
            long long distSq = (long long)dx*dx + (long long)dy*dy;
            insertDist(distTable, distSq, TABLE_SIZE);

            // 标准化向量，统计方向
            normalizeVector(&dx, &dy);
            insertDir(dirTable, dx, dy, TABLE_SIZE);
        }

        // 累加当前点的潜在等腰数
        for (unsigned int k = 0; k < TABLE_SIZE; k++) {
            DistFreqNode* node = distTable[k];
            while (node != NULL) {
                long long cnt = node->count;
                if (cnt >= 2) {
                    total += cnt * (cnt - 1) / 2;
                }
                node = node->next;
            }
        }

        // 累加当前点的退化三角形数
        for (unsigned int k = 0; k < TABLE_SIZE; k++) {
            DirFreqNode* node = dirTable[k];
            while (node != NULL) {
                long long cnt = node->count;
                if (cnt >= 2) {
                    collinear += cnt * (cnt - 1) / 2;
                }
                node = node->next;
            }
        }

        destroyDistTable(distTable, TABLE_SIZE);
        destroyDirTable(dirTable, TABLE_SIZE);
    }

    // 整数坐标无等边三角形，直接返回有效计数
    return total - collinear;
}

// 统计等边三角形数量（整数坐标下直接返回0）
long long countEquilateral(int N, int points[][2]) {
    (void)N;
    (void)points;
    return 0;
}

int main() {
    int N, T;
    char buffer[256];

    fgets(buffer, sizeof(buffer), stdin);
    sscanf(buffer, "%d %d", &N, &T);

    int (*points)[2] = malloc(N * sizeof(*points));
    if (!points) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < N; i++) {
        fgets(buffer, sizeof(buffer), stdin);
        sscanf(buffer, "%d %d", &points[i][0], &points[i][1]);
    }

    long long triangleCount;
    if (T == 1) {
        triangleCount = countIsosceles(N, points);
    } else {
        triangleCount = countEquilateral(N, points);
    }

    printf("%lld\n", triangleCount);

    free(points);
    return 0;
}

代码优化点说明 #

1. 时间复杂度降至O(n²)：每个点遍历其余n-1个点，哈希表操作均为O(1)平均时间，整体复杂度远优于原O(n³)。
2. 利用整数坐标特性：直接返回等边三角形数量为0，避免无效计算。
3. 哈希表针对性设计：分别统计距离频次和方向频次，精准计算潜在等腰数和退化数。
4. 避免重复计数：每个有效等腰三角形仅被统计一次（以唯一的顶点为基准），无需额外去重。

内容的提问来源于stack exchange，提问作者user17524053