У меня есть координаты различных точек в декартовой системе координат (координаты являются целыми числами), и мне нужно посчитать количество равносторонних и равнобедренных треугольников, которые я могу построить на их основе. Как я могу сделать это максимально эффективно и вовремя?
Я пишу код на 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;
}
Пожалуйста, перечитайте мой комментарий. Кроме того, вы не опубликовали никакого кода. SO означает, что у вас возникли проблемы/проблемы с определенным кодом/задачами. Просьба о лучших/более эффективных способах приведет только к самоуверенным ответам, которые также не по теме.
@DarkBee Насколько мне известно, вопросы об алгоритмах сами по себе явно по теме в Stack Overflow.
@RobbyCornelissen при расчете количества треугольников, расчет расстояния, я думаю, трудно улучшить)
Я удалил свой ответ на данный момент, потому что он очень неверен. Возможно, вы также сможете попытать удачу на cs.stackexchange.com
Ваши координаты целые или с плавающей запятой?
Я хотел бы увидеть ваш код решения: как вы справились с неточностью чисел с плавающей запятой, из-за которой вы могли пропустить совпадение в вашей хеш-таблице? Вы уверены, что ваше решение действительно работает?
@trincot Извините, числа целые, я отредактировал вопрос
Если все координаты целые числа, то равносторонних треугольников не существует. См. Равносторонний треугольник, вершины которого являются точками решетки?. Может быть, я что-то упускаю?
@trincot Действительно, спасибо, гениальное решение) Можете ли вы мне помочь с равнобедренными треугольниками?
Конечно, но это требует серьезного обновления вашего вопроса.
@trincot Конечно, вопрос исправлен)
Что касается равносторонних треугольников, мы можем быть краткими: поскольку все точки имеют целочисленные координаты, равносторонних треугольников не существует, как указано в Равносторонний треугольник, вершины которого являются точками решетки?
Чтобы найти равнобедренные треугольники, вы можете использовать такой подход:
Для каждой точки подсчитайте, сколько равнобедренных треугольников можно составить, причем эта точка является соединением двух ребер одинакового размера, следующим образом (на точку):
Предполагая, что добавления и обновления хэш-карт имеют среднюю временную сложность O(1), общая временная сложность равна O(𝑛²), с 𝑛 количеством входных точек.
@DarkBee Мой код работает, но я ищу алгоритм для эффективного решения этой проблемы, поскольку мой работает медленно.