有效计算可以从一组点构造的等边和等腰三角形的数量

Question

我有笛卡尔坐标系中各个点的坐标（坐标是整数），我需要计算可以在它们上构造的等边三角形和等腰三角形的数量。我怎样才能尽可能高效地及时完成这项工作？

我正在用 C 编写代码，并尝试将所有可能的点对之间的距离存储在哈希表中，这样我就不必再次计算距离，但我确信有一个更有效的解决方案。

我的代码：

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

#define TABLE_SIZE 10007 // Prime number for table size

typedef struct {
    int firstPoint[2]; // Coordinates of point 1
    int secondPoint[2]; // Coordinates of point 2
    int distanceSquared; // Distance squared between points
} HashTableEntry;

unsigned int jenkins_hash(const void *key, size_t length) {
    const unsigned char *data = key;
    unsigned int hash = 0;
    size_t i;

    for (i = 0; i < length; ++i) {
        hash += data[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

unsigned int hash(int firstPoint[2], int secondPoint[2]) {
    unsigned char key[8];
    memcpy(&key[0], &firstPoint[0], sizeof(int));
    memcpy(&key[4], &secondPoint[0], sizeof(int));
    return jenkins_hash(key, sizeof(key)) % TABLE_SIZE;
}

void insert(HashTableEntry** table, int firstPoint[2], int secondPoint[2], int distanceSquared) {
    unsigned int index = hash(firstPoint, secondPoint);
    while (table[index] != NULL) {
        index = (index + 1) % TABLE_SIZE; // Linear probing
    }
    table[index] = (HashTableEntry*)malloc(sizeof(HashTableEntry));
    if (table[index] == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    memcpy(table[index]->firstPoint, firstPoint, sizeof(int) * 2);
    memcpy(table[index]->secondPoint, secondPoint, sizeof(int) * 2);
    table[index]->distanceSquared = distanceSquared;
}

int getDistanceSquared(HashTableEntry** table, int firstPoint[2], int secondPoint[2]) {
    unsigned int index = hash(firstPoint, secondPoint);
    HashTableEntry* entry;
    while ((entry = table[index]) != NULL) {
        if (entry->firstPoint[0] == firstPoint[0] && entry->firstPoint[1] == firstPoint[1] &&
            entry->secondPoint[0] == secondPoint[0] && entry->secondPoint[1] == secondPoint[1]) {
            return entry->distanceSquared; // Distance squared found
        }
        index = (index + 1) % TABLE_SIZE; // Linear probing
    }
    return -1; // Distance squared not found
}

int calculateDistanceSquared(int x1, int y1, int x2, int y2) {
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

// Function to count the number of isosceles triangles
int countIsoscelesTriangles(int N, int points[][2], HashTableEntry** table) {
    int count = 0;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int distSquared_ij = getDistanceSquared(table, points[i], points[j]);
            for (int k = j + 1; k < N; ++k) {
                int distSquared_ik = getDistanceSquared(table, points[i], points[k]);
                int distSquared_jk = getDistanceSquared(table, points[j], points[k]);
                if (distSquared_ij == distSquared_ik || distSquared_ij == distSquared_jk || distSquared_ik == distSquared_jk) {
                    count++;
                }
            }
        }
    }
    return count;
}

// Function to count the number of equilateral triangles
int countEquilateralTriangles(int N, int points[][2], HashTableEntry** table) {
    int count = 0;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int distSquared_ij = getDistanceSquared(table, points[i], points[j]);
            for (int k = j + 1; k < N; ++k) {
                int distSquared_ik = getDistanceSquared(table, points[i], points[k]);
                int distSquared_jk = getDistanceSquared(table, points[j], points[k]);
                if (distSquared_ij == distSquared_ik && distSquared_ij == distSquared_jk) {
                    count++;
                }
            }
        }
    }
    return count;
}

void destroyHashTable(HashTableEntry** table) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        free(table[i]);
    }
    free(table);
}

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 == NULL) {
        fprintf(stderr, "Memory allocation failed\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]);
    }

    HashTableEntry** table = calloc(TABLE_SIZE, sizeof(HashTableEntry*));
    if (table == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int distanceSquared = calculateDistanceSquared(points[i][0], points[i][1], points[j][0], points[j][1]);
            insert(table, points[i], points[j], distanceSquared);
        }
    }

    int triangleCount;
    if (T == 1) {
        triangleCount = countIsoscelesTriangles(N, points, table);
    } else {
        triangleCount = countEquilateralTriangles(N, points, table);
    }

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

    destroyHashTable(table);
    free(points);

    return 0;
}

Answer 1

关于等边三角形，我们可以简短地说：由于所有点都有整数坐标，因此不存在等边三角形，如顶点为格点的等边三角形？

中指出的那样

要找到 等腰 三角形，您可以采用以下方法：

对于每个点，计算用该点作为两个相等大小的边之间的连接可以形成多少个等腰三角形，如下（每个点）：

• 填充一个以距离为键的新哈希图，并使用相应的值来计算距当前点的距离有多少个点。
• 对于此哈希图中的每个计数 𝑘，将 𝑘(𝑘−1)/2 添加到等腰三角形的总数。

假设 hashmap 添加和更新的平均时间复杂度为 O(1)，则整体时间复杂度为 O(𝑛²)，其中 𝑛 为输入点数。