Перечислить все различные максимальные подмножества точек, лежащих на одной прямой - C (СИ)
Формулировка задачи:
Добрый день
Хочу попросить форумчан в составлении алгоритма, ибо самому не получается
Задача:
Задано множество точек на плоскости. Перечислить все различные максимальные подмножества точек, лежащих на одной прямой, которые содержат более 2х точек.
Решение задачи: «Перечислить все различные максимальные подмножества точек, лежащих на одной прямой»
textual
Листинг программы
/*Задано множество точек на плоскости. Перечислить все
различные максимальные подмножества точек, лежащих на
одной прямой, которые содержат более 2х точек.
*/
#include <stdio.h>
#include <stdlib.h>
struct POINT
{ int x,y;
};
/*============ создаем подмножества точек, лежащих на одной прямой ========*/
void FillSets (int **sets, POINT **p, int N, int M)
{ int i, j, m = 0, k;
for (i = 0; i<N-1; i++)
for (j = i+1; j<N; j++, m++)
{ for (k = 0; k<N; k++)
if((p[k]->x - p[i]->x) * (p[j]->y - p[i]->y) == (p[k]->y - p[i]->y)*(p[j]->x - p[i]->x))
sets[m][k] = 1;
}
}
/*================= вывод всех подмножеств на консоль =====================*/
void ShowSets (int **sets, int N, int M)
{ int i,j;
printf("Subsets created:\n");
for (i = 0; i<M; i++)
{ for (j = 0; j<N; j++)
printf("%5d", sets[i][j]);
printf("\n");
}
printf("\n");
}
/*================= проверка двух подмножеств на равенство ================*/
int SetsAreEqual (int *set1, int *set2, int N)
{ int i= 0;
while (i<N)
if (set1[i] != set2[i])
return 0;
else
i++;
return 1;
}
/*============= удаление подмножества (зануление всех членов) ==============*/
void EraseSet (int *set, int N)
{ int i = 0;
while (i<N)
set[i++] = 0;
}
/*======================= оставляем только уникальные наборы ================*/
void LeaveUniques (int **sets, int N, int M)
{ int i,j;
for (i = 0; i<M-1; i++)
for (j = i+1; j<M; j++)
if (SetsAreEqual (sets[i], sets[j], N))
EraseSet (sets[j], N);
}
/*========= выводим максимальные подмножества (к-во точек не менее трех) ======*/
void Results (int **sets, int N, int M)
{ int i, j, sum;
printf("Maximum subsets found for these points:\n\n");
for (i = 0; i<M; i++)
{ for (j = 0, sum = 0; j<N; j++)
sum += sets[i][j];
if (sum > 2)
{ for (j = 0; j<N; j++)
if (sets[i][j])
printf("%5d", j);
printf("\n");
}
}
}
int main()
{ /*на входе - файл с данными: в первой строке N
дальше - в каждой строке пара чисел - координаты точек
*/
FILE *in = fopen("data.txt", "r");
int N, i = 0, j, **sets, M;
char buf[20];
fgets(buf, 20, in);
sscanf(buf, "%d", &N);
POINT **p = (POINT**) malloc (N * sizeof(POINT*));
while(i<N)
p[i++] = (POINT*) malloc(sizeof(POINT));
i = 0;
while(i<N)
{ fgets(buf, 20, in);
sscanf(buf, "%d%d", &(p[i]->x), &(p[i]->y));
i++;
}
/*данные считаны. Приступаем к созданию подмножеств точек,
лежащих на одной прямой
*/
M = N*(N-1)/2;
sets = (int**) malloc (M * sizeof(int*));
i = 0;
while(i<M)
sets[i++] = (int*) malloc (N * sizeof(int));
for (i = 0; i<M; i++)
for (j = 0; j<N; j++)
sets[i][j] = 0;
FillSets (sets, p, N, M);
ShowSets (sets, N, M);
/*подмножества созданы. Удаляем повторяющиеся
*/
LeaveUniques (sets, N, M);
/*выводим результат
*/
Results (sets, N, M);
i = 0;
while(i<M)
free (sets[i++]);
free (sets);
i = 0;
while(i<N)
free (p[i++]);
free (p);
fclose (in);
getchar();
return 0;
}
Объяснение кода листинга программы
В этом коде реализована задача поиска максимальных подмножеств точек на плоскости, лежащих на одной прямой. Вот список действий, выполняемых в коде:
- Считывание входных данных из файла
data.txt. В первой строке считывается количество точек (N). Затем, в каждой строке считываются координаты пары точек. - Создание структуры данных для представления точек (структура POINT).
- Создание массива указателей на точки (POINT** p) и заполнение его считанными координатами.
- Создание массива (M) для хранения максимальных подмножеств точек.
- Создание двумерного массива (int** sets) для хранения подмножеств.
- Заполнение двумерного массива (FillSets) значениями, которые определяют, принадлежит ли точка к подмножеству.
- Вывод всех подмножеств на консоль (ShowSets).
- Удаление повторяющихся подмножеств (EraseSet).
- Оставление только уникальных наборов (LeaveUniques).
- Вывод результатов (Results).
- Освобождение памяти, выделенной под массивы точек и подмножеств.
- Закрытие файла
data.txt. - Ввод символа для подтверждения выполнения программы.
- Возврат 0, что означает успешное выполнение программы.