/*
 *
 * Autor: Kamil Derynski <kamil@derynski.net>
 *
 * Program prezentuje działanie algorytmu grahama dla konkretnego problemu.
 * 
 *  - Dla wylosowanego zbioru punktów na płaszczyźnie (3<=n<=100) znaleźć minimalny obrys wypukły. Wyniki zapisujemy do pliku.
 *  - Kod jest bardzo bałaganiarski, ale dobrze i jasno minimalnym nakładem sił prezentuje działanie algorytmu do powyższego zadania.
 *  - Część implementująca sam algorytm Grahama została zaczęrpnieta ze strony algorytm.org w opracowaniu Michała Knasickiego i przepisana z C++/STL na ANSI C.
 *
 */

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

#define ROZMIAR 10

///Dla wylosowanego zbioru punktów na płaszczyźnie (3<=n<=100) znaleźć minimalny obrys wypukły, Wyniki zapisać do plików.


//Struktura reprezentująca punkt
typedef struct {
	int x;
	int y;
}Tpunkt;

//Struktura wyniku, punkt oraz współczynnik alfa
typedef struct {
	int x;
	int y;
	float alfa;
}Twynik;

typedef struct wezel{
	Twynik punkt;
	struct wezel *next;
}Twezel;

//Implementacja stosu na liscie jednokierunkowej
Twezel *head = NULL;
Twynik gPopPunkt;

void pop(void) {
	Twezel *link;
	Twynik punkt;

	if(head == NULL ){
		printf("Stos pusty !\n");
		return ;
	}
	else {
		link=head->next;
		punkt = head->punkt;
		head=link;
		gPopPunkt = punkt;
		printf("Zdejmuje ze stosu punkt - (%d,%d)\n",punkt.x,punkt.y);
	}
}

void push(Twynik punkt){
	Twezel *link;
	link = malloc (sizeof(Twezel));
	link->punkt=punkt;
	link->next = head;
	head = link;
	printf("Wkladam na stosu punkt - (%d,%d)\n",link->punkt.x,link->punkt.y);
}

void NDBGpop(void) {
	Twezel *link;
	Twynik punkt;

	if(head == NULL ){
		printf("Stos pusty !\n");
		return ;
	}
	else {
		link=head->next;
		punkt = head->punkt;
		head=link;
		gPopPunkt = punkt;
		printf("Zdejmuje ze stosu punkt - (%d,%d)\n",punkt.x,punkt.y);
	}
}

void NDBGpush(Twynik punkt){
	Twezel *link;
	link = malloc (sizeof(Twezel));
	link->punkt=punkt;
	link->next = head;
	head = link;
	printf("Wkladam na stosu punkt - (%d,%d)\n",link->punkt.x,link->punkt.y);
}

void showStack(Twezel *top){
	printf("\nAktualny stan stosu\n");
	printf("-------------------\n");
	Twezel *tmp;
	tmp = top;
	int i = 0;
	while(top != NULL){
		printf("Element %d - (%d,%d)\n",i,top->punkt.x,top->punkt.y);
		top = top->next;
		i++;
	}
	top = tmp;
	printf("-------------------\n\n");
}

//koniec sekcji stosu

//Wektor wynikowy
Twynik wynik[ROZMIAR];

//funkcja generujaca losowa wartosc
/*int rnd(int min, int max) {
  if (max>=min) {
    max -= min;
  } else {
    int tmp = min - max;
    min = max;
    max = tmp;
  }
 return max ? rand() % max + min : min;
}
*/
int rnd(int min, int max){
	int random_number = min + (int)rand () * (max - min + 1) / RAND_MAX;
	return random_number;
}

//Funkcja sortująca wektor wynik wg współczynnika alfa
void quicksort_1(int x, int y) {
	int i,j;
	float v;
	Twynik temp;
	i=x;
	j=y;
	v=wynik[div(x+y,2).quot].alfa;
	do{
		while (wynik[i].alfa<v) i++;
   		while (v<wynik[j].alfa) j--;
   		if (i<=j){
        	temp=wynik[i];
      		wynik[i]=wynik[j];
      		wynik[j]=temp;
      		i++;
      		j--;
		}
	}
	while (i<=j);
	if (x<j) quicksort_1(x,j);
	if (i<y) quicksort_1(i,y);
}

//Funkcja sortująca wektor wynik wg współrzędnej x (punkty o takim samym alfa)
void quicksort_2(int x, int y) {
	int i,j;
	float v;
	Twynik temp;
	i=x;
	j=y;
	v=wynik[div(x+y,2).quot].x;
	do{
		while (wynik[i].x<v) i++;
		while (v<wynik[j].x) j--;
		if (i<=j){
			temp=wynik[i];
			wynik[i]=wynik[j];
			wynik[j]=temp;
			i++;
			j--;
		}
	}
	while (i<=j);
	if (x<j) quicksort_2(x,j);
	if (i<y) quicksort_2(i,y);
}


/*Funkcja szuka w wektorze przedziału <i,j>, w którym punkty
  mają taki sam współczynnik alfa, a na stepnie sortuje ten
  przedział wg współrzędnej x*/
void sortuj(void) {
	int i=0;
	int j;
	Twynik tmp;
	Twynik swp;
	int pos = 0;

	//Znajdź przedział <i,j> o wspólnym alfa
	do{
		if (wynik[i].alfa==wynik[i+1].alfa){
			j=i;
			do
				j++;
			while (wynik[i].alfa==wynik[j].alfa);
				j--;

			//Posortuj ten przedział
   			quicksort_2(i,j);
   			i=j;
   		} else
   		i++;
 	}
	while (i<ROZMIAR);
}

Twynik findStart(void) {
	Twynik tmp;
	int i;
	int pos;
	tmp = wynik[0];
	for(i=0;i<ROZMIAR;i++){
		if(tmp.x > wynik[i].x) {
			tmp = wynik[i];
			pos = i;
		}
	}
	for(i=0;i<ROZMIAR;i++){
		if(tmp.x == wynik[i].x && tmp.y > wynik[i].y){
			tmp = wynik[i];
			pos = i;
		}
	}
	return wynik[pos];
}


//-------------------------------------------
//algorytm grahama
//-------------------------------------------

//Funkcja oblicza wyznacznik macierzy 3x3 (metodą Sarrusa)
int det(Twynik p1, Twynik p2, Twynik p3){
	printf("\nObliczam wyznacznik dla: (%d,%d) - (%d,%d) - (%d,%d)\n",p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);
	return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}


//Funkcja sprawdza, czy przechodząc do punktu p3 skręcamy w prawo (1), czy w lewo (0)
int skret_w_prawo(Twynik p3){
	Twynik p2;
	Twynik p1;

	//Pobieramy ze szczytu stosu punkt p2 oraz punkt p1, bedacy tuż pod szczytem
	if(head != NULL && head->next != NULL){
		p2=head->punkt;
		NDBGpop();
		p1=head->punkt;
		NDBGpush(p2);
	}
	else
		return 0;

	//Punkt p3 leży po lewej stronie wektora p1->p2
	if (det(p1,p2,p3)>0)
		return 0;
	//Punkt p3 leży po prawej stronie wektora p1->p2
	else
		return 1;
}

//-----------------------------------
// main
//-----------------------------------

int main(void){

srand(time(NULL)); //startowe ziarno dla funkcji losujacej

FILE *wp;
wp =fopen("wynik.txt", "a+");

//Wektor wejściowy
Tpunkt wektor[ROZMIAR];

//Zmienne pomocnicze
Tpunkt p;
Twynik w;

//Czynnik d=|x|+|y|
float d;

//Współczynnik alfa
float alfa;

int it = 0;
int it2 = 0;

//tworzymy ROZMIAR losowych punktów
for (it =0; it < ROZMIAR; it++) {
	p.x=rnd(3,ROZMIAR);
	p.y=rnd(3,ROZMIAR);
	wektor[it] = p;
}

///Test
/*
p.x=2;
p.y=2;
wektor[0] = p;

p.x=3;
p.y=4;
wektor[1] = p;

p.x=6;
p.y=5;
wektor[2] = p;

p.x=10;
p.y=4;
wektor[3] = p;

p.x=4;
p.y=3;
wektor[4] = p;

p.x=6;
p.y=4;
wektor[5] = p;
*/

////Obliczamy wartosc d oraz alfa
for (it = 0; it < ROZMIAR; it++) {
	p=wektor[it];
	d=abs(p.x)+abs(p.y);

	if ((p.x>=0)&&(p.y>=0))
	 alfa=p.y/d;

	if ((p.x<=0)&&(p.y>=0))
 	 alfa=2-p.y/d;

	if ((p.x<=0)&&(p.y<=0))
	 alfa=2+abs(p.y)/d;

	if ((p.x>=0)&&(p.y<0))
	 alfa=4-abs(p.y)/d;

	//Zapisz punkt i wspolczynnik do wektora wynikowego
	w.x=p.x;
	w.y=p.y;
	w.alfa=alfa;
	wynik[it2] = w;
	it2++;
}

//-------------------------------------

//Posortuj wektor wynikowy wg wartości czynnika alfa
quicksort_1(0,ROZMIAR-1);

//Posortuj punkty o takim samym alfa wg współrzędnej x
sortuj();

//Wypisz wynik
printf("Posortowane punkty\n");
printf("-------------------\n");
for (int i=0;i<ROZMIAR;i++) {
	w=wynik[i];
	printf("Punkt #%d: (%-2d,%-2d)\talfa=%.3f\n",i+1,w.x,w.y,w.alfa);

}
printf("-------------------\n\n");

//algorytm grahama

Twynik punkt;
Twynik start; //punkt startowy

start = findStart();

//Początek algorytmu

//Umieszczamy 3 pierwsze punkty na stosie
push(start); //element o najmniejszym x i y
push(wynik[0]);
push(wynik[1]);

//pokazujemy aktualny stan stosu
showStack(head);

printf("-------- Jazda ---------\n");

for (int i=3;i<ROZMIAR;i++){
	while (skret_w_prawo(wynik[i])==1){
		showStack(head);
		pop();
		printf("^^\n");
	}
	push(wynik[i]);


}

//wynik
printf("\n------ WYNIK -------\n");
printf("\nPunkty tworzace wypukla otoczke: \n");
showStack(head);

//wyniki do pliku

fprintf(wp,"Dla punktów: \n");
for (int k=0; k < ROZMIAR; k++) {
	fprintf(wp,"(%d,%d) ",wynik[k].x,wynik[k].y);
}
fprintf(wp,"\nMinimalny obrys wypukly tworza nastepujace punkty: \n");
while(head != NULL){
	fprintf(wp,"(%d,%d) ",head->punkt.x,head->punkt.y);
	NDBGpop();
}


return 0;
}