//ALGO2 IS1 213B LAB10
//Nataniel Antosik
//an44260@zut.edu.pl

#include<iostream>
#include<vector>
#include<fstream>
#include<time.h>
#include<string>
#include<vector>

using namespace std;

class Punkty {
public:
	double x, y;			//współrzędne
	int indeks;				//numer obiektu
	Punkty(double x, double y, int indeks) {	//przekazujemy dane do tworzenia obiektu
		this->x = x;		//nadajemy im wartości i numer danemu obiektowi
		this->y = y;
		this->indeks = indeks;
	}
	Punkty() {}				//pusty konstruktor dla tablicy
	~Punkty() {}				//destruktor
};

int CMP(Punkty point1, Punkty point2) { //Comparator Graham, przekazujemy dwa obiekty z tablicy
	double cross_prod = (point1.y * point2.x) - (point2.y * point1.x); //cross, sprawdzamy czy punkt, jest na lewo czy na prawo od poprzedniego
	if (cross_prod > 0.0) //jest na lewo
		return 1;
	if (cross_prod < 0.0) //jest na prawo
		return -1;
	return 0;
}

int CMP3pkt(Punkty point1, Punkty point2, Punkty point3) { //komperator 3 punktowy, działa tak samo jak 2 pkt tylko sprawdza kąt od punktu (0.0,0.0)
	double cross_prod = (point1.y - point3.y) * (point2.x - point3.x) - (point2.y - point3.y) * (point1.x - point3.x);
	if (cross_prod > 0.0) //jest na lewo podwzględem kąta
		return 1;
	if (cross_prod < 0.0) //jest na prawo podwzględem kąta
		return -1;
	return 0;
}

void merge(Punkty * tablica, int start, int s, int koniec)
{
	Punkty* tmp1 = new Punkty[(s - start + 1)];	// utworzenie tablicy pomocniczej lewej
	Punkty* tmp2 = new Punkty[(koniec - s)];		// utworzenie tablicy pomocniczej prawej
	int i = start, j = s + 1, k = 0;			// zmienne pomocnicze

	while (i <= s && j <= koniec) {				// Skopiowanie danych do tablicy pomocniczej
		if (CMP3pkt(tablica[i], tablica[j], tablica[0]) < 0) { //sprawdzamy kąt i, j podwzględem kątu elementu 0
			tmp1[k] = tablica[j]; //przypisujemy do prawego
			j++;
		}
		else {
			tmp1[k] = tablica[i]; //przypisujemy do lewego
			i++;
		}
		k++;
	}

	if (i <= s) {
		while (i <= s) {
			tmp1[k] = tablica[i]; //do tablicy przypisujemy wartości z tmp
			i++;
			k++;
		}
	}
	else {
		while (j <= koniec) {
			tmp2[k] = tablica[j]; //przypisujemy do lewego
			j++;
			k++;
		}
	}
}

void merge_Sort(Punkty * tablica, int start, int koniec)
{
	int s; //środek
	if (start != koniec) {
		s = (start + koniec) / 2;
		merge_Sort(tablica, start, s);			// Dzielenie lewej części
		merge_Sort(tablica, s + 1, koniec);		// Dzielenie prawej części
		merge(tablica, start, s, koniec);		// Łączenie części lewej i prawej
	}
}

vector<Punkty> convex_Hull(Punkty * tab, int N) {		//przekazujemy tablice obiektów (czyli punkty), i rozmiar
	vector<Punkty> wynik;								//wetkor wynikowy
	wynik.push_back(tab[0]);							//dodajemy pierszwe trzy elementy do naszego wektora wynikowego
	wynik.push_back(tab[1]);
	wynik.push_back(tab[2]);
	merge_Sort(tab, 1, N);
	if (CMP(wynik[1], wynik[2]) > 0) {					//Comperator dla pierwszego i drugiego elementu, jeżeli zwróci 1 to
		swap(wynik[1], wynik[2]);						//zamieniamy miejscami obiekty w wektorze
		wynik.pop_back();								//usuwamy ostatni element w wektorze
	}
	for (int i = 3; i < N; i++) {						//przypadek dla kolejnych elementów
		int rozmiar = wynik.size() - 1;					//rozmiar dla naszego wektora wynikowego
		if (CMP(wynik[rozmiar], tab[i]) < 0) {			//Comperator dla pierwszego i drugiego elementu, jeżeli zwróci 1 to
			wynik.pop_back();							//nowy element jest na prawo więc usuwamy
			wynik.push_back(tab[i]);					//dodajemy kolejny element do sprawdzania
		}
		else { wynik.push_back(tab[i]); }				//przypadek nowy punkt jest na lewo czyli działa poprawnie
	}
	return wynik;
}

void znajdzMIN(Punkty tab[], int N) {
	int minimum = tab[0].indeks;				//zapisujemy sobie pierwszy indeks jako minimum
	for (int i = 1; i < N; i++) {				//pętla po każdym obiekcie
		if (tab[i].y < tab[minimum].y) {		//szukamy najmniejszego y
			minimum = tab[i].indeks;
		}
		else if (tab[i].y == tab[minimum].y) {	//przypadek kiedy y są równe
			if (tab[i].x < tab[minimum].x) {	//szukamy najmniejszego x
				minimum = tab[i].indeks;
			}
		}
	}

	swap(tab[minimum].x, tab[0].x);				//zamieniamy wszystkie dane z znalezionego minimum
	swap(tab[minimum].y, tab[0].y);
	swap(tab[minimum].indeks, tab[0].indeks);

	for (int j = N - 1; j >= 0; j--) {			//przechodzimy od końca do początku i odejmujemy wartości od minimum
		tab[j].x = tab[j].x - tab[0].x;
		tab[j].y = tab[j].y - tab[0].y;
	}
}


int main()
{
	vector<Punkty> convex;
	int n, x, y, indeks;
	fstream plik;
	plik.open("points1.txt");
	if (plik.good())
	{
		cout << "Znaleziono plik" << endl;
	}
	else {
		cout << "Nie znaleziono pliku" << endl;
		exit(0);
	}

	plik >> n;								//ilość wszystkich punktów
	Punkty* tablica = new Punkty[n];		//tworzymy wskaźnik na tablice obiektów o rozmiarze podanym jako pierwsza wartość z pliku
	for (int i = 0; i < n; i++) {			//pętla dodająca nowe obiekty
		plik >> tablica[i].x;				//przypisujemy do nowego obiektu wartości x i y z układu współrzędnych
		plik >> tablica[i].y;
		tablica[i].indeks = i;				//nadajemy indeks nowemu obiektowi
	}
	plik.close(); //zamykamy plik

	cout << "Ilosc elementow: " << n << endl;
	for (int i = 0; i < n; i++) {
		cout << "Wartosci w indeksie " << tablica[i].indeks << " x: " << tablica[i].x << " y: " << tablica[i].y << endl;
	}
	cout << "MIN" << endl;
	znajdzMIN(tablica, n);
	cout << "Ilosc elementow: " << n << endl;
	for (int i = 0; i < n; i++) {
		cout << "Wartosci w indeksie " << tablica[i].indeks << " x: " << tablica[i].x << " y: " << tablica[i].y << endl;
	}
	convex = convex_Hull(tablica, n);

	cout << "Ilosc elementow: " << n << endl;
	for (int i = 0; i < n; i++) {
		cout << "Wartosci w indeksie " << convex[i].indeks << " x: " << convex[i].x << " y: " << convex[i].y << endl;
	}

}