#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>


typedef struct bases                        /*a bázis adatait tároló struktúra: a címe, meg a következőre mutató pointer*/
{
    unsigned int x;
    unsigned int y;
    struct bases *nbase;
}base;
typedef struct gyereks
{
    int sm;                             /*sent money: az elküldött pénz*/
    int ajándéklista[26];             /*az ajándék lista, a betűk ASCII kódjának megfelelő eltolásával, hogy azt megfeltetthessük az artombbel*/
    unsigned int x;                     /*a házuk koordinátája*/
    unsigned int y;
    int szabad;                         /*igaz/hamis: feldolgoztuk-e már(később bővebben)*/
    struct gyereks* ngyerek;            /*a következő gyerekre mutató pointer*/
}gyerek;
int artomb[26];



double tavolsag(unsigned ax, unsigned ay, unsigned bx, unsigned by)
{
    double osszeg=(ax-bx)*(ax-bx);
    osszeg +=(ay-by)*(ay-by);
    return sqrt(osszeg);
}/////////tavolsag

int utikoltseg(double szam)                         /*a kapott szám felső egészrészét (megkezdett kilométerét) ceil függvény segítségével megadom, majd szorzom kettővel az egységár miatt*/
{
    int rcost=0;
    double kerekitett=ceil((szam/1000));            /*rcost=road cost*/
    return rcost=(int)2*kerekitett;
}///////utikoltseg

base *new_base_list()                                   /*Új base elemekből álló listát hoz létre*/
{
    base *stre=(base*)malloc(sizeof (base));            /*Egy első és hátsó strázsát tartalmaz*/
    base *stru=(base*)malloc(sizeof (base));
    if(stre&&stru)
    {
        stre->x=0;
        stre->y=0;
        stre->nbase=stru;
        stru->x=0;                                      /*A rendezés miatt célszerű 0-nak venni az értékait a hátsó strázsának*/
        stru->y=0;
        stru->nbase=NULL;
        return stre;
    }
    else                                                /*Ha nem jött létre az egyik strázsa, akkor a másik se legyen már ott :D*/
    {
        if(!stru)
            free(stre);
        if(!stre)
            free(stru);
        return NULL;
    }
}//////////new_base_list

base *new_base(unsigned int h, unsigned int v)                  /*horizontal és vertical változókat kap a listaelemet feltöltő függvény*/
{
    base*helye=(base*)malloc(sizeof(base));
    if(helye)                                                   /*ha le tudta foglalni és nem nullát adott vissza*/
        helye->x=h;
        helye->y=v;
        helye->nbase=NULL;
    return helye;
}//////////new_base

base* add_base(base* stre)                                      /*Bázisokat beolvasó és tároló függvény*/
{
    unsigned int hori, verti, k, i=0;
    base *spot, *temp;                                          /*Mivel rendezem is egyből, kell ennyi változó*/
    FILE *fp=fopen("BASE.DAT","rb");
    if(!fp)                                                     /*Ha hibásan nyitná meg a filet:*/
    {
        printf("An error occured during the opening of the file.\n");
        return 0;
    }
    while (fread (&k, sizeof (unsigned int), 1, fp) != 0)       /*A ciklus addig megy, amíg az fread nem ad vissza 0-t*/
    {
        if(i%2==0)
            verti=k;
        else
        {
            hori=k;
            temp=new_base(hori, verti);                         /*A rendezésnél a legkeletibb kell, az lesz az első elemem, hogy strázsa arra mutasson*/
            spot=stre;                                          /*A rendezésnél mindig a lista első elemével kell kezdeni, hogy biztosan jó értéket adjon*/
            for(spot; spot->nbase!=NULL; spot=spot->nbase)
            {
                if(hori>spot->nbase->x)                         /*A legkeletibb bázist teszi az első helyre*/
                {
                    temp->nbase=spot->nbase;
                    spot->nbase=temp;
                    break;                                      /*Ha nem break-elnék, akkor végtelen ciklusban maradna, mert a temp az nem NULL*/
                }
            }
        }
        i++;
    }
    fclose(fp);
    return stre;                                                /*Az első elem címét kell visszaadni az eljárás végeztélvel.*/
}//////// add_base

void arak()                                                     /*beolvassa fajlbol az egyes ajandekok arait, ezt pedig egy tombben tarolja*/
 {
        int i;
        FILE *fp = fopen("PRICE.DAT", "rb");                    /*Globális változóba ovlassa be*/
        if(!fp)
        {
            printf("An error occured during the opening of the file.\n");
            exit(1);
        }
        for(i=0;i<26;i++)
            fread(&artomb[i], sizeof(int), 1, fp);
        fclose(fp);
 }//////////arak

gyerek *new_gyerek_list()                                   /*Új base elemekből álló listát hoz létre*/
{
    gyerek *stre=(gyerek*)malloc(sizeof (gyerek));          /*Egy első és hátsó strázsát tartalmaz*/
    gyerek *stru=(gyerek*)malloc(sizeof (gyerek));
    if(stre&&stru)
    {
        int i;
        stre->sm=0;                                         /*A strázsák minden elemét nullára, vagy NULL-ra veszem*/
        stre->x=0;
        stre->y=0;
        stre->szabad=1;
        stre->ngyerek=stru;
        for (i=0; i<26; i++)
            stre->ajándéklista[i] = '\0';
        stru->sm=0;
        stru->x=0;
        stru->y=0;
        stru->szabad=1;
        stru->ngyerek=NULL;
        for (i=0; i<26; i++)
            stru->ajándéklista[i] = '\0';
        return stre;
    }
    else                                                    /*Ha nem jött létre az egyik strázsa, akkor a másik se legyen már ott :D*/
    {
        if(!stru)
            free(stre);
        if(!stre)
            free(stru);
        return NULL;
    }
}/////////////new_gyerek_list

gyerek *new_gyerek(unsigned int h, unsigned int v, unsigned sent_money, int ajlista[])      /*horizontal és vertical változókat kap a listaelemet feltöltő függvény*/
{
    gyerek*minden=(gyerek*)malloc(sizeof(gyerek));
    if(minden)                                              /*ha le tudta foglalni és nem nullát adott vissza*/
    {
        int i;
        for(i=0; i<26; i++)
            minden->ajándéklista[i]=ajlista[i];
        minden->x=h;
        minden->y=v;
        minden->sm=sent_money;
        minden->ngyerek=NULL;
        minden->szabad=1;

    }
    return minden;
}//////////new_gyerek

int base_distance(base* hova, base* east, unsigned verti, unsigned hori)    /*Meghatározza, hogy keleti bázishoz van-e a legközelebb a gyerek*/
{
    double dmin=1.79769e+308, d=0;                          /*distance rövidítések, a minimumot először a double-n tárolható maximális értéknek veszem*/
    base* temp;
    for(hova; hova->nbase!=NULL; hova=hova->nbase)          /*A hova-t léptetem végig, az eleinte a strázsára mutat, majd a távolság függvényemmel megadom a minimális távolságot.
                                                            A strázsa értékével sem hasonlítom össze! A kapott értéket egy temp-ben tárolom, hogy ne break-eljek.*/
    {
        d=tavolsag(hova->x, hova->y, hori, verti);
        if(d<=dmin)
        {
            dmin=d;
            temp=hova;                                      /*Itt kibreak-elhetnék, de inkább kerülöm annak a használatát, ezért kerül egy temp-be a bázishoz tartozás*/
        }
    }
    if(temp==east)
    {
        return 1;
    }
    return 0;
}//////////base_distance

gyerek* add_gyerek(gyerek* stre, base* belso)               /*A gyerekkel*-al fog visszatérni, a base* (base elso röviden=belso) ahhoz kell, hogy csak azokat a gyerekeket
                                                            vegyem fel, akik a legkeletibb bázishoz tartoznak (rendezés miatt az első elem a strázsa után)*/
{
    FILE* fp=fopen("GIFT.TXT", "rt");
    char c;                                                 /*ajándéklista, verti, hori és sm a file-ból kiolvasott: x,y koordináták és az elküldött pénz*/
    int ajándéklista[26];
    unsigned verti, hori, i, k=0, sm;
    int igaz=0;
    gyerek* temp=stre, *spot=stre;

    while(fscanf(fp,"%d %d\n", &verti, &hori)!=EOF)
    {
        for (i=0; i<26;i++) ajándéklista[i] = '\0';           /*kinullázza a tömböt*/
        while((c = fgetc(fp)) && c != '\n')
        {
            if (c > 64)
            {
                ajándéklista[k] = c - 65;                 /*ASCII kódolás szerint az A-tól való távolaságot mondja meg*/
                k++;                                        /*amikor megnézem, akkor csak a k-adik elemig kell néznem(a 0-ák miatt)*/

            }
        }
        k=0;
        fscanf(fp, "%d", &sm);
        if(igaz=base_distance(belso->nbase, belso->nbase, verti, hori)) /*Paraméterek: a belso az a bázis lista első strázsája, a rendezés miatt a belso->nbase a legkeletibb bázis. A többi pedig a két koordináta. Ha igaz a függvény értéke, akkor eltárolom a gyereket.*/
        {
            temp=new_gyerek(verti, hori, sm, ajándéklista);
            temp->ngyerek=spot->ngyerek;                        /*A spot segítségével elrakom, majd */
            spot->ngyerek=temp;
            spot=spot->ngyerek;
        }
    }
    return stre;
    fclose(fp);
}/////////////add_gyerek

gyerek* find_north_gyerek(gyerek* stre)
{
    gyerek* spot=stre->ngyerek, *temp=stre;                     /*Lépgeteő spot, segéd temp, ebben tárolom a visszaadandó gyerek címét*/
    unsigned int max=0;
    while(spot->ngyerek)
    {
        if(max<spot->x)
        {
            max=spot->x;
            temp=spot;
        }
        spot=spot->ngyerek;
    }
    return temp;
}/////////////find_north_gyerek

double bejaras(base* east, gyerek*elsoh, gyerek* north)         /*Visszatér a legészakibb gyerekhez tartozó út hosszával
                                                                változók: east: a keleti bázis, elsoh: az első nem strázs a gyerek listában, north: az északi gyerek*/
{
    double d=0, dmin=1.79769e+308;                              /*d a változó távolság, dmin pedig a minimum távolság: először a double-n tárolható maximális érték*/
    gyerek* temp=elsoh, *spot=elsoh, *haz=elsoh;                /*elsoh-val megjegyzem az első elemet, ami majd a "rendezéseknél" lesz fontos, temp, spot és ház pedig szbadon változtatható változók*/
    while(haz->ngyerek!=NULL)                                   /*megnézi az összes gyerek címét és kiválasztja a minimálisat*/
    {
        d=tavolsag(east->x, east->y, haz->x, haz->y);
        if(d<=dmin)
        {
            dmin=d;
            temp=haz;                                           /*Ha találtunk egy minimálisat, akkor azt eltároljuk*/
        }
        haz=haz->ngyerek;
    }
    temp->szabad=0;                                             /*A ciklus végén a minimálisnak át kell írni a szabad változóját 0-ra: ezzel jelzem, hogy abba a bázisba már nem mehet újra út*/
    haz=temp;
    for(haz; haz!=north; haz=temp)                              /*Mindegyik házból kell kiindulási pont egészen addig, amíg el nem érjük a keresett gyereket, akkor leállhat*/
    {
        spot=elsoh;                                             /*Az összehasonlítást mindig a lista első elemétől kell kezdeni, ezért a spot-ot visszaállítom*/
        dmin=1.79769e+308;                                      /*maximálisra állítom a dmint, hogy biztos találjak rövidebb utat*/
        while(spot->ngyerek!=NULL)                              /*Az összes gyerekkel összehasonlítom a kiválaszottat (haz), feltéve, hogy a szabad=1, tehát még nem vezetett bele út*/
        {
            if(spot->szabad)
            {
                d=tavolsag(haz->x, haz->y, spot->x, spot->y);
                if(d<=dmin)
                {
                    dmin=d;
                    temp=spot;
                }
            }
            spot=spot->ngyerek;
        }
        temp->szabad=0;                                         /*A temp-be tárolom a szükséges adatot*/
    }
    return dmin;                                                /*Amikor leáll a nagy for ciklus, akkor pont a north-ba mutató út hosszát fogja a dmin tartalmazni és épp arra van szükségünk.*/
}//////////// bejaras

int osszkoltseg(gyerek *north, int uk)                          /*északi gyerek és útikötlség*/
{
    int osszeg=0m k;
    artomb[i]=north->ajándéklista[i]
    for(k=0; k<i; k++)




}////// osszkoltseg

int main()
{
    double uthossz=0;
    gyerek* gyp, *gylista, *north;
    base* bp, *blista;
    bp=new_base_list();
    blista=add_base(bp);
    gyp=new_gyerek_list();
    gylista=add_gyerek(gyp, bp);
    north=find_north_gyerek(gyp);
    uthossz=bejaras(bp->nbase, gyp->ngyerek, north);
    return 0;
}