Pojebane Cytrynki z Spoja

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
// http://pl.spoj.com/problems/LEMONS/ na algorytmie Dijkstry
//----------------struktury---------------------

struct Point
{
    int x, y;
} point;                //struktura przechowujaca punkt,

struct Edge
{
    int from;
    int to;
    int length;
} edge;                 //struktura przechowujaca wezel


//----------------metody---------------------

void loadFile();                                        //funkcja wczytujaca zawartosc pliku
int getDistance(struct Point, struct Point b);          //funkcja obliczajaca odleglosc miedzy dwoma punktami
int comparator(const void *p, const void *q);           //funkcja okreslajaca wartosc porownania dla
                                                        //algorytmu quickSort, przy sortowaniu struktur Edge
void fillAllEdgesTable();                               //funkcja wypelniajaca tablice ze wszystkimi krawedziami

int checkDidExistConnectionBetweenNodes(struct Edge* list, int counter, int from, int to);      //utworzenie grafu na podstawie krawedzi wezlow
                                                                                                //i sprawdzenie czy istnieje sciezka miedzy a i b
void printEdgeTable(struct Edge *list, int counter);    //funkcja pomocnicza, opcjonalna - wydruk tablicy
void DFS(int i);
//----------------zmienne---------------------
//*p to to samo co p[]
//**p to to samo co p[][]
//robimy tak, bo nie mozemy zrobic p = int[zmienna], mozemy tylko stalych wartosci uzywac np. p = int[5], w innym przypadku musimy uzywac alokowania
//na tablice za pomoca funkcji malloc

struct Point *p;                //tablica przechowujaca punkty
struct Edge *edges;             //tablica przechowujaca wszystkie krawedzie sciezki miedzy punktami
struct Edge *resultEdgeTree;    //tablica przechowujaca krawedzie wynikowego drzwa spinajacego

int size;                       //ilosc punktow
int allEdgesCounter;            //ilosc wszystkich krawedzi
int spanningTreeEdgeSize;       //ilosc krawedzi wynikowego drzewa spinajacego

//DFS
int** x;                        //tymczasowe drzewo (macierz sasiedztwa) utworzona na podstawie aktualnie wybranych krawedzi
int *visited;                   //lista odwiedzonych wierzcholkow w X
int searched;                   //wierzcholek do ktorego sprawdzamy czy istnieje polaczenie
int finded;                     //wynik wyszukiwania sciezki

int main(){
    loadFile();             //wczytyujemy wartosci z pliku i wypelniamy tablice points
    fillAllEdgesTable();    //wypelniamy tablice edges bazujac na tablicy points

    //http://www.geeksforgeeks.org/comparator-function-of-qsort-in-c/
    //sortowanie tablicy wg. regul opisanych w metodzie comparator(porówmując) sortujemy tablice z krawedziami wg. ich dlugosci

    qsort((void*)edges, allEdgesCounter, sizeof(edges[0]), comparator);     //sortuje z funkcji bibliotecznej
    //mamy posortowana tablice ze wszystkimi krwedziami w grafie, teraz probujemy je dodawac do tablicy
    //z krawiedziami wynikowymi, jesli nowo dodawana krawedz powoduje powstanie cyklu (sciezka z a->b juz istnieje, pomijamy);
    int i;                              //licznik petli
    int actualResultCounter = 0;        //licznik aktualnie dodanych wezlow do tablicy wynikowej programu

    for(i=0;i<allEdgesCounter;i++){         //iterujemy (przechodzimy) po wszystkich krawedziach

        int exist = checkDidExistConnectionBetweenNodes(resultEdgeTree, actualResultCounter, edges[i].from, edges[i].to);   //Na podstawie zawartosci tabeli wyiników jest tworzony graf
        if(exist == 0){                                                                                                     //sprawdzamy czy w grafie istnieje polaczenie miedzy wezlami badanej krawedzi
            resultEdgeTree[actualResultCounter] = edges[i];     //jesli nie, dodajemy do zbioru krawedzi wynikowych badana krawedz
            actualResultCounter++;
        }
    }

    int sum = 0;
    for(i=0;i<spanningTreeEdgeSize;i++){
        sum+=resultEdgeTree[i].length;
    }

    printEdgeTable(resultEdgeTree, spanningTreeEdgeSize);

    printf("SUMA: %d",sum);
    //sumujemy wartosci podajemy wynik

    return 1;
}

void fillAllEdgesTable(){
    int i, j, nodeCounter = 0;      //deklaracja
    //tworzymy polaczenie miedzy dowolnymi dwoma wierzcholkami (punktami) i dodajemy do tablicy addEdgesCounter,
    for(i = 0 ; i < size ; i++){
        //porownujemy tylko z elemenentami nastepujacymi po porownywanym, poniewaz odleglosc a -> b jest taka sama jak b -> a
        for(j= i+1; j < size; j++){
            //dodanie krawedzi do tablicy wszystkich krawedzi (edges)
            edges[nodeCounter].from = i;
            edges[nodeCounter].to = j;
            edges[nodeCounter].length = getDistance(p[i],p[j]);
            nodeCounter++;
        }
    }
}

//utworzenie grafu na podstawie krawedzi wezlow i sprawdzenie czy istnieje sciezka miedzy a i b
int checkDidExistConnectionBetweenNodes(struct Edge* list, int counter, int from, int to){
    //tablica dwuwymiarowa (baba w babie)
    //mamy tabele o rozmiarze counter * counter - macierz sasiedztwa

    //zadeklarowanie "zewnetrznej tablicy"
    x = malloc(size * sizeof(int*));

    //ilosc elementow w liscie
    //parametr wejsciowy counter

    int i,j;
    for (i = 0; i < size; i++) {
        x[i] = malloc(size * sizeof(int));  //zaalokowanie pamieci dla "wewnetrznej" tablicy
    }

    for(i=0; i<size; i++){
        for(j=0;j<size; j++){
            x[i][j] = 0;    //czyszczenie tablicy, wypelnienie zerami
        }
    }

    //wypelnienie tabeli krawedziami
    //counter jest nam potrzebny w celu ograniczenia przeglądanych elementow tablicy , np. ma ona przeznaczone miejsce na 9 krawedzi (tyle bedzie koncowo) ale aktualnie jest tam tylko jedna,
    //w tym przypadku do macierzy sasiedztwa dodajemy tylko ten pierwszy element
    for(i=0; i<counter;i++){
        x[list[i].from][list[i].to] = 1;
        x[list[i].to][list[i].from] = 1;
    }

    visited = malloc(size * sizeof(int));   //DFS - tablica zawierajaca odwiedzone przez algorytm wierzcholki, alokacja miejsca

    for(i=0;i<size;i++){
        visited[i] = 0;                     //wyzerowanie tablicy odwiedzonych wierzcholkow
    }

    DFS(from);                              //wywolanie algorytmu rekurencyjnego DFS z poczatkiem w wierzcholku FROM
    if(visited[to]==1){
        return 1;
    } else {
        return 0;
    }
}

//algorytm wyszukiwania DFS
void DFS(int i)
{
    int j;
    visited[i]=1;

    for(j=0;j<size;j++){
       if(!visited[j] &&x [i][j] == 1){
            DFS(j);
       }
    }

}

//funkcja pomocnicza, opcjonalna - wydruk tablicy intow(długości krawędzi)
void printIntTable(int ** list, int counter){
    int i,j;
    for(i=0; i<counter; i++){
        for(j=0;j<counter;j++){
            printf("%d ", list[i][j]);
        }
        printf("\n");
    }
}

//funkcja pomocnicza, opcjonalna - wydruk tablicy krawedzi
//*list --> list[]
void printEdgeTable(struct Edge *list, int counter){
    int i;
    printf("Printing table elements\n");
    for(i=0; i<counter;i++){
        printf("\t%d. from: %d, to: %d,  length: %d\n", i, list[i].from, list[i].to, list[i].length);
    }
}

//wczytywanie z pliku
void loadFile(){

    //plik z ktorego czytamy
    const char* fileName = "Dane.txt";
    //otwarcie pliku w trybie odczytu
    FILE* file = fopen(fileName, "r");
    //bufor, zakladamy ze linia ma nie wiecej niz 256 znakow
    char line[256];
    //zmienne do ktorych wczytamy wspolrzedne punktow
    int x, y;
    //licznik(counter) przeczytanych punktów -1 linia
    int counter = -1;
    //tak dlugo jak mamy co czytac
    while (fgets(line, sizeof(line), file)) {
        //pobieranie za pomoca wzorca wartosci x,y z pobranej linii
        sscanf(line,"%d %d",&x,&y);
        //counter == -1, zeby nie brac pod uwage przy umieszczaniu w tablicy pierwszej linijki
        if(counter == -1){
            //jesli pierwsza linia, ilosc pkt
            counter = 0;
            //podglad pierwszej linijki 10
            size = x;
            //inicjalizacja tablicy struct Point[size] w ktorej beda wspolrzedne punktow ;
            p = malloc(sizeof(struct Point)*size);  //funkcja malloc rezerwuje ilosc pamieci na tablice,
                                                    //przykladowo dla size = 5, wywolanie malloc(sizeof(Struct Point)*size) da taki sam efekt jak p = struct Point[5];
        } else { //inna linijka niz pierwsza dodanie do kolejnych indeksow tablicy wspolrzednych pkt x,y (uzupełnienie tabeli)
            p[counter].x = x;   //do elementow struktury odwolujemy sie przez kropke
            p[counter].y = y;
            //zwiekszenie licznika po dodaniu
            counter++;
        }
    }
    allEdgesCounter = size*(size-1)/2;          //ze wzoru na ilosc krawedzi w grafie: n*(n-1)/2
    spanningTreeEdgeSize = size - 1;            //ilosc krawedzi bedzie rowna ilosci wierzcholkow -1, gdyby byla rowna, mielibysmy obiekt zamkniety
    edges = malloc(sizeof (struct Edge)* (allEdgesCounter));        //rezerwowanie miejsca dla tablicy wynikow
    resultEdgeTree = malloc(sizeof (struct Edge) * (size - 1));     //deklaracja tablicy wynikowej
    fclose(file);
}

int getDistance(struct Point a, struct Point b)
{
    //wynik dzialania funkcji
    int distance;
    distance = (int)(sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) *(a.y-b.y)));
    return distance;
}

//funkcja sortujaca
int comparator(const void *p, const void *q)
{
    int l = ((struct Edge *)p)->length; //przez --> zamiast . bo uzywamy wskaznika na strukture a nie "obiektu" struktury
    int r = ((struct Edge *)q)->length;
    return (l - r);
}