I have the coordinates of various points in the Cartesian coordinate system (coordinates are integers) and I need to count the number of equilateral and isosceles triangles that I can construct on them. How can I do this as efficiently as possible in time?
I'm writing code in C and tried to store the distances between all possible pairs of points in a hash table so I don't have to count the distances again, but I'm sure there's a more efficient solution.
My code:
#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;
}
Concerning equilateral triangles we can be short: as all the points have integer coordinates, there are no equilateral triangles, as pointed out in Equilateral triangle whose vertices are lattice points?
To find the isosceles triangles you could take this approach:
For each point count how many isosceles triangles can be made with this point being the connection between the two equal-sized edges, as follows (per point):
Assuming hashmap additions and updates have an average time complexity of O(1), the overall time complexity is O(𝑛²), with 𝑛 the number of input points.