Перечислить все различные максимальные подмножества точек, лежащих на одной прямой - 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;
}

Объяснение кода листинга программы

В этом коде реализована задача поиска максимальных подмножеств точек на плоскости, лежащих на одной прямой. Вот список действий, выполняемых в коде:

  1. Считывание входных данных из файла data.txt. В первой строке считывается количество точек (N). Затем, в каждой строке считываются координаты пары точек.
  2. Создание структуры данных для представления точек (структура POINT).
  3. Создание массива указателей на точки (POINT** p) и заполнение его считанными координатами.
  4. Создание массива (M) для хранения максимальных подмножеств точек.
  5. Создание двумерного массива (int** sets) для хранения подмножеств.
  6. Заполнение двумерного массива (FillSets) значениями, которые определяют, принадлежит ли точка к подмножеству.
  7. Вывод всех подмножеств на консоль (ShowSets).
  8. Удаление повторяющихся подмножеств (EraseSet).
  9. Оставление только уникальных наборов (LeaveUniques).
  10. Вывод результатов (Results).
  11. Освобождение памяти, выделенной под массивы точек и подмножеств.
  12. Закрытие файла data.txt.
  13. Ввод символа для подтверждения выполнения программы.
  14. Возврат 0, что означает успешное выполнение программы.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.857 из 5
Похожие ответы