Перечислить все различные максимальные подмножества точек, лежащих на одной прямой - 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, что означает успешное выполнение программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д