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

typedef struct{ /* pontok koordinátáit tároló struktúra */
    unsigned int x;
    unsigned int y;
}pont;

typedef struct { /* adott házhoz szükséges információt tároló struktúra */
    pont koordinata; /* koordináták */
    int kizaras; /* a legközelebbi ház kereső függvénynél szükséges, hogy ne válasszuk ki ugyanazt */
}haz;

typedef struct{ /* adott bázioshoz szükséges információt tároló struktúra */
    pont koordinata; /* koordináták */
    char ajandek[27]; /* a bázishoz legközelebbi család ajándékai */
    unsigned int penz; /* a bázishoz legközelebbi család által beküldött pénz */
    unsigned int OsszTavDij; /* a bázishoz tartozó kiszámlázott távolságdíjak összege */
    double MinTav; /* a bázis és a hozzá legközelebb lévő ház távolsága */
}bazis;

typedef struct house{ /* házak listájának eleme */
    haz h; /* házhoz tartozó adatok */
    struct house *next; /* következő házra mutató pointer */
}hazelem,*hazpointer;

typedef struct base{ /* bazisok listájának eleme */
    bazis b; /* bázihoz tartozó adatok */
    struct base *next; /* követekező elemre mutató pointer */
    struct house *first; /* ehhez a bázishoz tartozó házak listájára mutató pointer */
}baziselem,*bazispointer;

bazispointer BazisBeszuras(bazis newdata,bazispointer head){ /* newdata változó berakása a verembe */
    bazispointer temp=malloc(sizeof(baziselem)); /* allokálás */
    temp->b=newdata; /* adatok berakása */
    temp->b.MinTav=-1; /* szükséges adatok nullázása későbbi feltétel miatt */
    temp->b.OsszTavDij=0; /* szükséges adatok nullázása későbbi feltétel miatt */
    temp->first=NULL; /* szükséges adatok nullázása későbbi feltétel miatt */
    temp->next=head; /* következő elemre irányítás */
    head=temp; /* head frissítése */
    return head;
}

bazispointer BazisokVerembe(bazispointer head){ /* bázisok beolvasása és elhelyezése egy veremben */
    FILE* in; /* fájl megnyitásához szükséges pointer */
    bazis newdata; /* ideiglenes változó, amibe kerülnek a beolvasott adatok */
    in = fopen( "C:/BASE.DAT" , "rb" ); /* fájl megnyitása */
    while(fread(&newdata.koordinata.y, sizeof(unsigned int), 1, in) && fread(&newdata.koordinata.x, sizeof(unsigned int), 1, in)){ /* koordináták beolvasása */
        head=BazisBeszuras(newdata,head); /* beolvasott elemek berakása a verembe */
    }
    fclose(in); /* fájl bezárása */
    return head; /* az első elemre mutató pointer visszaadása */
}

double tavolsag(pont p1,pont p2){ /* két pont közötti távolság kiszámítása */
    unsigned int s;
    double gyokd;
    unsigned int gyoki;
    if(p1.x<p2.x) { s=p1.x; p1.x=p2.x; p2.x=s; }
    if(p1.y<p2.y) { s=p1.y; p1.y=p2.y; p2.y=s; }
    gyokd=sqrt(((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); /* d(P1,P2)=sqrt((x1-x2)^2 + (y1-y2)^2) */
    gyoki=gyokd;
    if(((gyoki-1)*(gyoki-1))==((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))) return (gyoki-1);
    if((gyoki*gyoki)==((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))) return gyoki;
    return gyokd;
}
bazispointer LegkozelebbiBazis(pont newdata,bazispointer head){ /* egy ponthoz a legközelebbi bázis megkeresése */
    double DistTemp; /* az eddig vizsgált legkisebb távolság */
    bazispointer temp; /* a keresett bázisra mutató pointer */
    if(head){ /* első vizsgálásnál a DistTemp-nek nincs értéke, ezért eddig ehhez a bázishoz lesz a legközelebb */
        DistTemp=tavolsag(newdata,head->b.koordinata); /* a legkisebb távolság frissítése */
        temp=head; /* a keresett bázisra mutató pointer frissítése */
    }
    head=head->next; /* következő bázis */
    while(head){
        if(DistTemp>tavolsag(newdata,head->b.koordinata)){ /* ha közelebb van a vizsgált bázishoz, mint az eddig vizsgáltak közül a legközelebbihez */
            DistTemp=tavolsag(newdata,head->b.koordinata); /* a legkisebb távolság frissítése */
            temp=head; /* a keresett bázisra mutató pointer frissítése */
        }
        head=head->next; /* következő bázis */
    }
    return temp; /* a keresett bázisra mutató pointer visszaadása */
}
hazpointer HazBeszuras(haz newdata,hazpointer head){ /* ház beszúrása a listába */
    hazpointer temp=malloc(sizeof(hazelem)); /* allokálás */
    temp->h=newdata; /* adatok berakása */
    temp->h.kizaras=1; /* később használt feltétel beállítása kezdeti értékre */
    temp->next=head; /* következő elemre irányítás */
    head=temp; /* head frissítése */
    return head; /* head visszaadása */
}

void HazakBeolvasasa(bazispointer head){ /* házak bázisokhoz rendelése, majd felfűzése a fésű ágaira */
    FILE* in; /* fájl megnyitásához szükséges pointer */
    haz newdata; /* adatok beolvasására használt változó */
    char karakter; /* adatok beolvasására használt változó */
    bazispointer temp; /* keresett bázisra mutató pointer */
    in = fopen( "C:/GIFT.TXT" , "rt" ); /* fájl megnyitás */
    while(!feof(in)){ /* fájl végét jelző feltétel */
        fscanf(in,"%d %d\n",&newdata.koordinata.y,&newdata.koordinata.x); /* koordináták beolvasása */
        temp=LegkozelebbiBazis(newdata.koordinata,head); /* a házhoz legközelebbi bázis megkeresése */
        temp->first=HazBeszuras(newdata,temp->first); /* ház beszúrása a legközelebbi bázison kialakított verembe */
        if(temp->b.MinTav!=-1){ /* ha volt már ház ebben a veremben */
            if(temp->b.MinTav>tavolsag(newdata.koordinata,temp->b.koordinata)){ /* ha a most beolvasott ház a legközelebbi az eddigiek közül*/
                int i=0; /* stringen végigfutó változó */
                temp->b.MinTav=tavolsag(newdata.koordinata,temp->b.koordinata); /* távolság átírása */
                fscanf(in,"%c",&karakter); /* ajándéklista olvasása karakterenként */
                while(karakter!='\n'){ /* ajándéklista olvasása karakterenként sortörésig */
                    if(karakter!=' '){ /* ha nem space */
                        temp->b.ajandek[i]=karakter; /* karakter beírása stringbe */
                        i++; /* következő string elem */
                    }
                    fscanf(in,"%c",&karakter); /* következőő karakter */
                }
                temp->b.ajandek[i]='\0'; /* a string lezárása */
                fscanf(in,"%d\n",&temp->b.penz); /* a család által beküldött pénz beolvasása */
            }
            else { /* ha nem a most beolvastott a legközelebbi ház, az adatatok beolvasása használás nélkül */
                int kuka;
                fscanf(in,"%c",&karakter);
                while(karakter!='\n'){
                    fscanf(in,"%c",&karakter);
                }
                fscanf(in,"%d\n",&kuka);
            }
        }
        else { /* ha nem volt még ház ebben a veremben */
            int i=0; /* stringen végigfutó változó */
            temp->b.MinTav=tavolsag(newdata.koordinata,temp->b.koordinata); /* mivel még nem volt ház a veremben, ez a ház van jelenleg legközelebb a bázishoz, távolság beírása */
            fscanf(in,"%c",&karakter); /* ajándéklista olvasása karakterenként */
            while(karakter!='\n'){ /* ajándéklista olvasása karakterenként amíg az nem sortörés */
                if(karakter!=' '){ /* ha a beolvasott karakter nem space */
                    temp->b.ajandek[i]=karakter; /* a karakter stringbe írása */
                    i++; /* következő string elem */
                }
                fscanf(in,"%c",&karakter); /* következő karakter */
            }
            temp->b.ajandek[i]='\0'; /* sortörés után a string lezárása */
            fscanf(in,"%d\n",&temp->b.penz); /* család által küldött pénz beírása */
        }
    }
    fclose(in);
}

unsigned int TavolsagDijazas(double tavolsag){ /* Távolság (méterben) alapján kiküldött útiköltség */
    unsigned int tavolsagi; /* távolság km-ben intben */
    double tavolsagd; /* távolság km-ben double-ban */
    tavolsagi=tavolsag/1000.0;
    tavolsagd=tavolsagi;
    if(tavolsagd==tavolsag/1000.0) return 2*tavolsagi; /* ha az intbeli távolság egyenlő a doublebelivel (azaz km-ben egész a távolság) akkor a díja 2x a távolság */
    else return 2*(tavolsagi+1); /* ha nem egész a távolság, akkor van +1 megkezdett km */
}

hazpointer LegkozelebbiHaz(pont bazis, hazpointer head){ /* egy ponthoz legközelebbi ház megkeresése */
    double DistTemp; /* jelenlegi legrövidebb távolság */
    hazpointer temp=NULL; /* jelenlegi legközelebbi házra mutató pointer, ha nincs ilyen akkor NULL */
    int vege=1;
    while(vege && head){ /* amíg nincs vége a házak listájának */
        if(head->h.kizaras){ /* ha olyan házon vagyunk ahol a kizárási feltétel még 1 */
            DistTemp=tavolsag(bazis,head->h.koordinata); /* távolság átírása */
            temp=head; /* házra mutató pointer átírása */
            vege=0;
        }
        head=head->next; /* ha a kizárási feltétel már 0 (lásd később) akkor következő elem */
    }
    while(head){ /* amíg nem érünk a házak végére */
        if(head->h.kizaras && DistTemp>tavolsag(bazis,head->h.koordinata)){ /* ha olyan háznál vagyunk amit még nem zártunk ki és közelebb van mint az eddigi legközelebbi */
            DistTemp=tavolsag(bazis,head->h.koordinata); /* távolság átírása */
            temp=head; /* házra mutató pointer átírása */
        }
        head=head->next; /* követező ház */
    }
    return temp; /* ha a lista végére értünk, a legközelebbire mutató pointer visszaadása (ha nincs ilyen, akkor NULL) */
}
void BazisOsszTavDij(bazispointer head){ /* bázisokhoz tartozó távolságok miatt kiszámlázott díjak összege*/
    hazpointer TempLegkozelebbi; /* adott házhoz legközelebbi házra mutató pointer */
    pont TempBazis; /* adott ház pontja */
    while(head){ /* ha van még házta bázis */
        TempBazis=head->b.koordinata; /* adott pont a bázis pontja */
        TempLegkozelebbi=LegkozelebbiHaz(TempBazis,head->first); /* bázishoz legközelebbi ház megkeresése (ha nincs akkor NULL) */
        while(TempLegkozelebbi){ /* ha van még vizsgált ház */
            head->b.OsszTavDij+=TavolsagDijazas(tavolsag(TempBazis,TempLegkozelebbi->h.koordinata));
            TempLegkozelebbi->h.kizaras=0; /* kizárási feltétel átírása 0-ra */
            TempBazis=TempLegkozelebbi->h.koordinata; /* vizsgált pont átírása az előzőhöz talált legközelebbi pontra */
            TempLegkozelebbi=LegkozelebbiHaz(TempBazis,head->first); /* az új vizsgált ponthoz legközelebbi pont keresés */
        }
        head=head->next; /* következő bázis */
    }
}

void ArakBeolvasasa(unsigned int* arak){ /* árak beolvasása a mainben deklarált tömbbe */
    FILE* in; /* fájl megnyitásához használt pointer */
    int k; /* tömbön végigfutó változó */
    in = fopen("C:/PRICE.DAT" , "rb" ); /* fájl megnyitása */
    for(k=0;k<26;k++){ /* tömbön végigfutó ciklus */
        fread(&(arak[k]),sizeof(unsigned int),1,in); /* ár beolvasása */
    }
    fclose(in); /* fáj bezárása */
}

int main(){
    bazispointer bazisok=NULL; /* bázisok vermére mutató pointer */
    bazispointer HaziFeladat; /* a házi feladathoz szükséges bázisra mutató pointer */
    unsigned int arak[26], visszajaro, k; /* árak, házi feladathoz szükséges távolság km-ben intben, visszajáró, ajándéklista stringjén végigfutó változó */
    bazisok=BazisokVerembe(bazisok); /* bázisok beolvasása */
    HazakBeolvasasa(bazisok); /* házak felfűzése a bázisokra */
    BazisOsszTavDij(bazisok); /* bázisokhoz tartozó kiszámlázott díjak összegének kiszámolása */
    ArakBeolvasasa(arak); /* árak beolvasása */
    /* Ellenőrzés kiiratással
    while(bazisok){
    printf("(%d;%d) %lf %d %d %s\n",bazisok->b.koordinata.x,bazisok->b.koordinata.y,bazisok->b.MinTav,bazisok->b.OsszTavDij,bazisok->b.penz,bazisok->b.ajandek);
    while(bazisok->first){
        printf("(%d;%d)\n",bazisok->first->h.koordinata.x,bazisok->first->h.koordinata.y);
        bazisok->first=bazisok->first->next;
    }
    bazisok=bazisok->next;
    }
    return 0;
    */
    HaziFeladat=bazisok; /* keresett bázis beállítása az elsőre */
    bazisok=bazisok->next; /* következő bázis */
    while(bazisok){ /* amíg vannak bázisok */
        if(HaziFeladat->b.OsszTavDij>bazisok->b.OsszTavDij) HaziFeladat=bazisok; /* ha kevesebb díjat számlázott ki a bázis, mint az eddigi legkevesebb akkor a keresett bázis pointerének átírása */
        bazisok=bazisok->next; /* következő bázis */
    }
    visszajaro=HaziFeladat->b.penz; /* a család által küldött összeg beírása */
    visszajaro-=TavolsagDijazas(HaziFeladat->b.MinTav);
    for(k=0;k<26;k++){ /* ajándéklistán végigfutó ciklus */
        switch(HaziFeladat->b.ajandek[k]){ /* a következő betű megállapítása */
            /* ha lehetséges, akkor a visszajáróból az ajándék árának levonása, következő ajándék vizsgálása | ha nem akkor kilépés a ciklusból */
            case 'A': if(visszajaro>arak[0]) visszajaro-=arak[0]; else k+=26; break;
            case 'B': if(visszajaro>arak[1]) visszajaro-=arak[1]; else k+=26; break;
            case 'C': if(visszajaro>arak[2]) visszajaro-=arak[2]; else k+=26; break;
            case 'D': if(visszajaro>arak[3]) visszajaro-=arak[3]; else k+=26; break;
            case 'E': if(visszajaro>arak[4]) visszajaro-=arak[4]; else k+=26; break;
            case 'F': if(visszajaro>arak[5]) visszajaro-=arak[5]; else k+=26; break;
            case 'G': if(visszajaro>arak[6]) visszajaro-=arak[6]; else k+=26; break;
            case 'H': if(visszajaro>arak[7]) visszajaro-=arak[7]; else k+=26; break;
            case 'I': if(visszajaro>arak[8]) visszajaro-=arak[8]; else k+=26; break;
            case 'J': if(visszajaro>arak[9]) visszajaro-=arak[9]; else k+=26; break;
            case 'K': if(visszajaro>arak[10]) visszajaro-=arak[10]; else k+=26; break;
            case 'L': if(visszajaro>arak[11]) visszajaro-=arak[11]; else k+=26; break;
            case 'M': if(visszajaro>arak[12]) visszajaro-=arak[12]; else k+=26; break;
            case 'N': if(visszajaro>arak[13]) visszajaro-=arak[13]; else k+=26; break;
            case 'O': if(visszajaro>arak[14]) visszajaro-=arak[14]; else k+=26; break;
            case 'P': if(visszajaro>arak[15]) visszajaro-=arak[15]; else k+=26; break;
            case 'Q': if(visszajaro>arak[16]) visszajaro-=arak[16]; else k+=26; break;
            case 'R': if(visszajaro>arak[17]) visszajaro-=arak[17]; else k+=26; break;
            case 'S': if(visszajaro>arak[18]) visszajaro-=arak[18]; else k+=26; break;
            case 'T': if(visszajaro>arak[19]) visszajaro-=arak[19]; else k+=26; break;
            case 'U': if(visszajaro>arak[20]) visszajaro-=arak[20]; else k+=26; break;
            case 'V': if(visszajaro>arak[21]) visszajaro-=arak[21]; else k+=26; break;
            case 'W': if(visszajaro>arak[22]) visszajaro-=arak[22]; else k+=26; break;
            case 'X': if(visszajaro>arak[23]) visszajaro-=arak[23]; else k+=26; break;
            case 'Y': if(visszajaro>arak[24]) visszajaro-=arak[24]; else k+=26; break;
            case 'Z': if(visszajaro>arak[25]) visszajaro-=arak[25]; else k+=26; break;
        }
    }
    printf("%d\n",visszajaro); /* a megoldás kiiratása */
    return 0;
}