/********************************************************
*
*  KISS GERGO <neptun>
*
*  Hány € volt a számla összege annak a gyereknek az esetében,
* akinek lakcíme a leginkább északra esik azok közül a gyerekek közül,
* akiket arról a bázisról szolgáltak ki,
* amelyik mind közül a legdélebbre fekszik?
*
**********************************************************/

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


	double sqrt( double d )
{
		double min = 1.0, max = d;
		double mid;
		double midsquare;
		double EPS = 1E-5;
		while (max-min > EPS) {
				mid = (max+min)/2.0;
				midsquare = mid*mid;
				if (midsquare < d) {
						min = mid;
				} else {
						max = mid;
				}
		}

		return mid;
}



// egyirányú láncolt lista a bázisok tárolására
// tárolja: x és y koordináta
struct base_list {
   int x,y;
   struct base_list* next;
};
typedef struct base_list Base;

// kétirányú lista a legdélebbi bázishoz tartozó gyerekek tárolásához
typedef struct child_list{
	int x,y; // koordináták
	int gift_num, cash; // kért ajándékok száma; szülõ által befizetett pénz
	char gift[26]; // kért ajándékok betûjelei
	struct child_list* next; // következõ listaelem
	struct child_list* prev; // elõzõ listaelem
	double distance; // a kiszolgálás során az elõzõ megállótól való távolság
} Child;


/**********************************************************************
* a bázisok beolvasása a BASE.DAT fájlból
* visszatérünk a lista kezdõcímével
***********************************************************************/
Base* ReadBases(){

	FILE* f;
	int temp[2]; // átmeneti tároló a beolvasott koordinátapárnak
	Base* base_act; // ciklusváltozó
	Base* base_begin; // lista eleje

	// fájl megnyitása, nincs hibakezelés
	f = fopen("BASE.DAT", "r");

	// strázsának lefoglalunk egy listaelemet
	base_act = base_begin = (Base*)malloc(sizeof(Base));
	// ciklus amíg a fájl végére nem érünk,
	// minden ciklusban beolvasunk egy koordinátapárt majd létrehozzuk a megfelelõ listaelemet
	while( fread(temp, sizeof(int), 2, f) ){
		base_act->next = (Base*)malloc(sizeof(Base));
		base_act = base_act->next;
		// tempbe lett beolvasva x és y
		base_act->y = temp[0];
		base_act->x = temp[1];
	}
	// a lista végére is strázsát rakunk, melynek next pointere NULL
	base_act->next = (Base*)malloc(sizeof(Base));
	base_act = base_act->next;
	base_act->next = NULL;

	// fálj bezárása
	fclose(f);

	// visszatérés a bázisok listájának elejével
	return base_begin;
}


/*****************************************************************
* legdélebbi bázis megkeresése
*****************************************************************/
Base* findSouthestBase(Base* base_begin){
	Base* min = base_begin->next; // elsõ elem a listából
	Base* act; // ciklusváltozó

	// szokásos minimumkeresési algorutmus
	for (act = base_begin->next; act->next != NULL; act = act->next){
		if (act->y < min->y){
			min = act;
		}
	}

	// visszatérés a legdélebbi bázis mutatójával
	return min;
}


/**********************************************************************************
* legészakabbi olyan gyerekek megkeresése, akit a legdélebbi bázisról szolgálnak ki.
* visszatér a feltételnek megfelelõ gyerekek láncolt listájának elejével
* paraméterként a bázisok listáját és a legdélebbi bázist várja
***********************************************************************************/
Child* searchChildrenSouth(Base* baseBegin, Base* southestBase){
	FILE* f;
	int x, y, cash, i;
	Base* act = baseBegin; // ciklusváltozó
	Base* nearBase = NULL; // egy gyerekhez legközelebb esõ bázis
	double minDist; // bázisoktól való legkisebb távolság tárolására
	Child* child_begin; // gyerekek listájának eleje
	Child* j; // ciklusváltozó
	Child* child_act; // ciklusváltozó
	char temp[60]; // ajándékok ideiglenes tárolója

	//fájl megnyitása
	f = fopen("GIFT.TXT", "rt");

	// lista elejére létrehozzunk egy strázsa elemet.
	child_begin = child_act = (Child*)malloc(sizeof(Child));
	// amíg a fájl végére nem érünk egy egy gyerek adatait dolgozzuk fel.
	// a feldolgozás csak akkor történik meg ha az a legdélebbi bázishoz tartozik
	// egyébként az adataival nem foglalkozunk
	// a ciklus fejlécében egy gyerek koordinátáit olvassuk be
	while ( fscanf(f, "%d %d\n", &y, &x) != EOF ){

		minDist = 999999999.9; // kezdeti távolság
		// végig megyünk a bázisokon és kikeressül a gyerekhez legközelebb fekvõt
		for (act = baseBegin->next; act->next != NULL; act = act->next){
			// pitagórasz tétel alapján ha a távolság kisebb mint az eddig talált minimum
			// akkor ezt tekintjük a legközelebbi bázisnak
			if ( sqrt( (act->x-x)*(act->x-x) + (act->y-y)*(act->y-y)) < minDist ){
				minDist = sqrt((act->x-x)*(act->x-x) + (act->y-y)*(act->y-y));
				nearBase = act;
			}
		}

		// ha a legközelebbi bázis megegyezik a legdélebbivel akkor feldolgozzuk a gyerek adatait
		if (nearBase == southestBase){
			// listaelem létrehozása és feltöltése
			child_act->next = (Child*) malloc(sizeof(Child));
			child_act = child_act->next;
			child_act->x = x;
			child_act->y = y;
			child_act->gift_num = 0;
			// az ajándékok beolvasása egy ideiglenes tömbbe
			fgets(temp,60,f);
			// ebbõl kidobjuk a szóközöket
			for(i=0; temp[i]!='\0'; i++){
				if (temp[i] != ' ' && temp[i] != '\n'){
					child_act->gift[child_act->gift_num++] = temp[i];
				}
			}
			// a biztosnág kedvéért lezérjuk nullával
			child_act->gift[child_act->gift_num] = '\0';
			// az szülõk álltal adott összeg beolvasása
			fscanf(f, "%d\n",&cash);
			child_act->cash = cash;
		}
		else{
			// ha nem a legdélebbihez tartozik a gyerek akkor 2 sort beolvasunk de nem csinálunk velük semmit
			fgets(temp, 60, f);
			fgets(temp, 60, f);
		}
	} // while ciklus vége

	// lezéró strázsa létrehozása
	child_act->next = (Child*)malloc(sizeof(Child));
	child_act = child_act->next;
	child_act->next = NULL;

	//fájl lezárása
	fclose(f);

	// kétirányúsításhoz a visszafele mutató pointerek beállítása
	child_begin->prev = NULL;
	for (j = child_begin; j->next != NULL; j = j->next){
		j->next->prev = j;
	}

	// visszatérés a gyerekek listájával
	return child_begin;
}


/************************************************************************
* A gyerekek listáját rendezi a kiszállítási sorrendnek megfelelõen
* paraméterül a gyerekek listáját és az induló bázist várja
* a rendezés közben kiszámolja a kiszállítás során azt a távolságot amit az elõzõ megállótól megtettek
**************************************************************************/
void calcDistAndSort(Child* childBegin, Base* baseFrom){
	Child* i; // ciklusváltozó
	Child* j; // ciklusváltozó
	Child* minChild; // adott ponthoz legközelebbi gyerek
	double min; // legközelebbi gyerek távolsága adott ponttól

	// a strázsát felhasználjuk arra hogy a bázis koordinátáit tárolja
	// így lényegesen leegyszerûsödik a bejárási útvonal megtalálása
	childBegin->x = baseFrom->x;
	childBegin->y = baseFrom->y;

	// felállítjuk a távolság szerinti sorrendet
	for (i = childBegin; i->next->next != NULL; i = i->next){
		min = 9999999.9;
		// megkeressük az aktuálisan vizsgált megállóhoz (kezdetben a bázis) legközelebbi gyereket
		for (j = i->next; j->next != NULL; j = j->next){
			if ( sqrt((i->x - j->x)*(i->x - j->x) + (i->y - j->y)*(i->y - j->y)) < min ){
				min = sqrt((i->x - j->x)*(i->x - j->x) + (i->y - j->y)*(i->y - j->y));
				minChild = j;
			}
		}
		// a megtalált legközelebbi gyereket az adott pont mögé helyezzük át a listában
		minChild->prev->next = minChild->next;
		minChild->next->prev = minChild->prev;
		minChild->next = i->next;
		minChild->prev = i;
		minChild->next->prev = minChild;
		i->next = minChild;
		// távolság eltárolása
		minChild->distance = min;
	}
}


/**********************************************************************
* A feladat kérdésére (lásd fent) a választ ez a függvény számolja ki
* paraméterül a gyerekek listáját várja
* visszatérni meg a számla összegével fog
**********************************************************************/
int calcNorthestChildPrice(Child* childBegin){

	FILE* f;
	int prices[26]; // ajándékok árai
	int i; // ciklusváltozó
	int price=0; // számla összege
	Child* northestChild = childBegin->next; // legészakabbi gyerek
	Child* iter; // ciklusváltozó

	// az ajándékok árait tartalmazó fájl megnyitása, habakezeléssel nem foglalkozunk
	f = fopen("PRICE.DAT", "rb");
	// a 26 darab ajándék árainak beolvasása
	fread(prices, sizeof(unsigned int), 26, f);
	fclose(f);

	// legészakabbi gyerek megkeresése
	for (iter = childBegin->next; iter->next != NULL; iter = iter->next){
		if(iter->y > northestChild->y){
			northestChild = iter;
		}
	}

	// a szállítási költség kiszámítása amit a számla összegéhez adunk hozzá
	price += ((int)(northestChild->distance/1000)+1)*2;
	// levonjuk ezt a még felhasználható összegbõl
	northestChild->cash -= price;
	i = 0;
	// addig számlázzunk ki az ajándékokat amíg van rá elegendõ keret vagy amíg el nem fogynak a kért ajándékok
	while (northestChild->cash > prices[northestChild->gift[i]-'A'] && i<northestChild->gift_num){
		price += prices[northestChild->gift[i]-'A'];
		northestChild->cash -= prices[northestChild->gift[i]-'A'];
		i++;
	}

	// visszatérünk a számla végösszegével
	return price;
}


int main(){

	Base* southestBase; // legdélebbi bázis
	Base* baseBegin; // bázisok listája
	Child* childBegin; // gyerekek listája
	int price; //számla végösszege
	Base* jter, *jnext; // ciklusváltozók
	Child* iter; // ciklusváltozó

	// bázisok beolvasása
	baseBegin = ReadBases();
	// legdélebbi bázis megkeresése
	southestBase = findSouthestBase(baseBegin);
	// legdélebbi bázishoz tartozó gyerekek megkeresése
	childBegin = searchChildrenSouth(baseBegin, southestBase);
	// távolságok kiszámítása és ez alapján a gyerekek rendezése
	calcDistAndSort(childBegin, southestBase);
	// legészakibb gyerek számlája összegének kiszámítása
	price = calcNorthestChildPrice(childBegin);
	printf("%d\n", price);


	// dinamikusan foglalt változók felszabadítása
	for (jter = baseBegin->next; jter->next != NULL;  jter = jnext){
		jnext = jter->next;
		free(jter);
	}
	free(jnext);

	for ( iter = childBegin->next; iter->next != NULL; iter = iter->next){
		free(iter->prev);
	}
	free(iter->prev);
	free(iter);

	getchar();

	return 0;
}