#include <allegro.h>
#include <cmath>

class punkt{
public:
int x, y;
double a;

punkt *next;
punkt *prev;
};

punkt *head = NULL;
punkt *tail = NULL;

//NARYSUJ PUNKTY
int rys_pkt()
{
clear_to_color( screen, makecol( 255, 255, 255 ) );

punkt *nowy;

if(head != NULL)
{
nowy = head;
while(nowy != NULL)
{
circlefill( screen, nowy->x, nowy->y, 2, makecol( 0, 0, 255 ) );
nowy = nowy->next;
}
}
else
{
textprintf_ex( screen, font, 20, 20, makecol( 255, 0, 0 ), - 1, "Nie dodales jeszcze zadnego punktu!!!" );
}

return D_O_K;
}

//DODAWANIE PUNKTU
int add()
{
punkt *nowy = NULL;

while(true)
{
if(mouse_b == 1)
{
nowy = new punkt;
nowy->x = mouse_x;
nowy->y = mouse_y;
if(head == NULL)
{
nowy->next = NULL;
nowy->prev = NULL;
head = nowy;
tail = nowy;
}
else
{
nowy->next = NULL;
nowy->prev = tail;
tail->next = nowy;
tail = nowy;
}

circlefill( screen, nowy->x, nowy->y, 2, makecol( 0, 0, 255 ) );

while(mouse_b == 1){}
break;
}
else if(mouse_b == 2) return 0;
}

return 1;
}

//DODAWANIE PUNKTÓW
int dodawanie()
{
clear_to_color( screen, makecol( 255, 255, 255 ) );
head = NULL;
tail = NULL;

textprintf_ex( screen, font, 20, 20, makecol( 0, 0, 0 ), - 1, "ABY ZAKONCZYC DODAWANIE PUNKTOW WCISNIJ PPM" );

while(add())
{
add();
}

rys_pkt();

return D_O_K;
}

//OBLICZANIE ALFA
double alfa(punkt *k, int sx, int sy)
{
double a, d, x, y, pomx, pomy;

x = k->x - sx;
y = k->y - sy;

pomx = x;
pomy = y;

if(pomx < 0) pomx = -pomx;
if(pomy < 0) pomy = -pomy;

d = pomx + pomy;

//obliczanie alfa
if(x > 0 && y >= 0) a = pomy/d;
else if(x <= 0 && y > 0) a = 2 - (pomy/d);
else if(x < 0 && y <= 0) a = 2 + (pomy/d);
else if(x >= 0 && y < 0) a = 4 - (pomy/d);

return a;
}

//ZLICZACZ ILOSCI PUNKTOW
int licz()
{
punkt *nowy;
int licznik = 0;

if(head != NULL)
{
nowy = head;
while(nowy != NULL)
{
nowy = nowy->next;
licznik++;
}
}

return licznik;
}

//SPRAWDZANIE CZY PUNKT LEZY WEWNATRZ TRUJKATA
int spr(punkt *q1, punkt *q2, punkt *q3, int sx, int sy)
{
int pom_x = 800, pom_y = 300, licznik = 0;
float det1, det2, det3, det4;

//sprawdzenie czy prosta q2 pom przecina się z prosta O q1
det1 = sx*q1->y + q1->x*q2->y + q2->x*sy - q2->x*q1->y - sx*q2->y - q1->x*sy;
det2 = sx*q1->y + q1->x*pom_y + pom_x*sy - pom_x*q1->y - sx*pom_y - q1->x*sy;
det3 = pom_x*q2->y + q2->x*sy + sx*pom_y - sx*q2->y - pom_x*sy - q2->x*pom_y;
det4 = pom_x*q2->y + q2->x*q1->y + q1->x*pom_y - q1->x*q2->y - pom_x*q1->y - q2->x*pom_y;

if(det1 > 0) det1 = 1;
if(det1 == 0) det1 = 0;
if(det1 < 0) det1 = -1;

if(det2 > 0) det2 = 1;
if(det2 == 0) det2 = 0;
if(det2 < 0) det2 = -1;

if(det3 > 0) det3 = 1;
if(det3 == 0) det3 = 0;
if(det3 < 0) det3 = -1;

if(det4 > 0) det4 = 1;
if(det4 == 0) det4 = 0;
if(det4 < 0) det4 = -1;

if(det1 != det2 && det3 != det4) licznik++;

//sprawdzenie czy prosta q2 pom przecina się z prosta O q3
det1 = sx*q3->y + q3->x*q2->y + q2->x*sy - q2->x*q3->y - sx*q2->y - q3->x*sy;
det2 = sx*q3->y + q3->x*pom_y + pom_x*sy - pom_x*q3->y - sx*pom_y - q3->x*sy;
det3 = pom_x*q2->y + q2->x*sy + sx*pom_y - sx*q2->y - pom_x*sy - q2->x*pom_y;
det4 = pom_x*q2->y + q2->x*q3->y + q3->x*pom_y - q3->x*q2->y - pom_x*q3->y - q2->x*pom_y;

if(det1 > 0) det1 = 1;
if(det1 == 0) det1 = 0;
if(det1 < 0) det1 = -1;

if(det2 > 0) det2 = 1;
if(det2 == 0) det2 = 0;
if(det2 < 0) det2 = -1;

if(det3 > 0) det3 = 1;
if(det3 == 0) det3 = 0;
if(det3 < 0) det3 = -1;

if(det4 > 0) det4 = 1;
if(det4 == 0) det4 = 0;
if(det4 < 0) det4 = -1;

if(det1 != det2 && det3 != det4) licznik++;

//sprawdzenie czy prosta q2 pom przecina się z prosta q1 q3
det1 = q1->x*q3->y + q3->x*q2->y + q2->x*q1->y - q2->x*q3->y - q1->x*q2->y - q3->x*q1->y;
det2 = q1->x*q3->y + q3->x*pom_y + pom_x*q1->y - pom_x*q3->y - q1->x*pom_y - q3->x*q1->y;
det3 = pom_x*q2->y + q2->x*q1->y + q1->x*pom_y - q1->x*q2->y - pom_x*q1->y - q2->x*pom_y;
det4 = pom_x*q2->y + q2->x*q3->y + q3->x*pom_y - q3->x*q2->y - pom_x*q3->y - q2->x*pom_y;

if(det1 > 0) det1 = 1;
if(det1 == 0) det1 = 0;
if(det1 < 0) det1 = -1;

if(det2 > 0) det2 = 1;
if(det2 == 0) det2 = 0;
if(det2 < 0) det2 = -1;

if(det3 > 0) det3 = 1;
if(det3 == 0) det3 = 0;
if(det3 < 0) det3 = -1;

if(det4 > 0) det4 = 1;
if(det4 == 0) det4 = 0;
if(det4 < 0) det4 = -1;

if(det1 != det2 && det3 != det4) licznik++;

if(licznik % 2 == 0) return 0;
else return 1;
}

//GRAHAM
int graham()
{
clear_to_color( screen, makecol( 255, 255, 255 ) );
int sx = 0, sy = 0, max_y = 600;
punkt *nowy;
punkt *nowy2;
punkt *pom;
punkt *pom2;
punkt *s;
punkt *q;
bool zamiana;
int n;

if(licz() < 3)
{
textprintf_ex( screen, font, 20, 20, makecol( 255, 0, 0 ), - 1, "ZA MALO PUNKTOW, DODAJ MINIMUM 3!!!" );
}
else
{
//rys_pkt();
n = licz();
//obliczanie centroidu
nowy = head;
while(nowy != NULL)
{
sx += nowy->x;
sy += nowy->y;
nowy = nowy->next;
}
sx = sx/n;
sy = sy/n;
//obliczanie wspolczynnikow alfa
nowy = head;
while(nowy != NULL)
{
nowy->a = alfa(nowy, sx, sy);
nowy = nowy->next;
}
//sortowanie punktow
while(true)
{
nowy = head;
nowy2 = nowy->next;
zamiana = false;
while(nowy->next != NULL)
{

if(nowy->a > nowy2->a)
{
zamiana = true;

int pomx = nowy->x;
int pomy = nowy->y;
double poma = nowy->a;
nowy->x = nowy2->x;
nowy->y = nowy2->y;
nowy->a = nowy2->a;
nowy2->x = pomx;
nowy2->y = pomy;
nowy2->a = poma;
}
nowy = nowy->next;
nowy2 = nowy2->next;
/*
if(nowy == head)
{
if(nowy->a > nowy->next->a)
{
zamiana = true;

pom = nowy->next;
nowy->next = nowy;
nowy->next->next = pom->next;
pom->next = nowy->next;
nowy = pom;
head = nowy;
}
nowy = nowy->next;
}
else if(nowy->next == tail)
{
if(nowy->a > nowy->next->a)
{
zamiana = true;

pom = nowy->next;
nowy->next = nowy;
nowy->next->next = pom->next;
pom->next = nowy->next;
nowy = pom;
tail = nowy->next;
tail->next = NULL;
}
nowy = nowy->next;
}
else
{
if(nowy->a > nowy->next->a)
{
zamiana = true;

pom = nowy->next;
nowy->next = nowy;
nowy->next->next = pom->next;
pom->next = nowy->next;
nowy = pom;
}
nowy = nowy->next;
}
*/
}
if(!zamiana) break;
}

rys_pkt();
//circlefill( screen, sx, sy, 2, makecol( 255, 0, 0 ) );

//szukanie punktu o najmniejszym y
nowy = head;
while(nowy->next != NULL)
{
if(nowy->y < max_y)
{
max_y = nowy->y;
s = nowy;
}
nowy = nowy->next;
}

//ustawienie head i tail tak zeby zapetlic liste
tail->next = head;
head->prev = tail;
//usuwanie punktow nie nalezacych do otoczki
q = s;
while(q->next != s)
{
if(spr(q, q->next, q->next->next, sx, sy) == 1)
{
q->next = q->next->next;
q->next->prev = q;
if(q != s) q = q->prev;
}
else q = q->next;
}
//rysowanie otoczki
q = s;
while(q->next != s)
{
line( screen, q->x, q->y, q->next->x, q->next->y, makecol( 255, 0, 0 ) );
q = q->next;
}
line( screen, q->x, q->y, q->next->x, q->next->y, makecol( 255, 0, 0 ) );
//ustanienie head na punkt s oraz tail na punkt s->prev
pom = s;
pom2 = s->prev;

pom->prev = NULL;
pom2->next = NULL;

head = pom;
tail = pom2;
}

return D_O_K;
}
//JARVIS
int jarvis()
{
clear_to_color( screen, makecol( 255, 255, 255 ) );

if(licz() < 3)
{
textprintf_ex( screen, font, 20, 20, makecol( 255, 0, 0 ), - 1, "ZA MALO PUNKTOW, DODAJ MINIMUM 3!!!" );
}
else
{
//algorytm
}

return D_O_K;
}
//CZYSZCZENIE EKRANU
int czysc()
{
clear_to_color( screen, makecol( 255, 255, 255 ) );

return D_O_K;
}
//KONIEC
int quitter()
{
return D_CLOSE;
}

//MENU

MENU file_menu[] =
{
{ "&Wyczysc ekran", czysc, NULL, 0, NULL },
{ "", NULL, NULL, 0, NULL },
{ "&Wyjscie", quitter, NULL, 0, NULL },
{ NULL, NULL, NULL, 0, NULL }
};

MENU zadania_menu[] =
{
{ "&Graham", graham, NULL, 0, NULL },
{ "&Jarvis", jarvis, NULL, 0, NULL },
{ "&Dodaj punkty", dodawanie, NULL, 0, NULL },
{ "&Narysuj punkty", rys_pkt, NULL, 0, NULL },
{ NULL, NULL, NULL, 0, NULL }
};

MENU main_menu[] =
{
{ "&Plik", NULL, file_menu, 0, NULL },
{ "&Zadania", NULL, zadania_menu, 0, NULL },
{ NULL, NULL, NULL, 0, NULL }
};

/* glowny dialog */

DIALOG main_dialog[] =
{
/* (dialog proc) (x) (y) (w) (h) (fg) (bg) (key) (flags) (d1) (d2) (dp) */
{ d_clear_proc, 0, 0, 800, 600, 0, 0, 0, 0, 0, 0, NULL },
{ d_menu_proc, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, main_menu },
{ NULL, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, NULL }
};

int main()
{
allegro_init();
install_keyboard();
install_mouse();
install_timer();
set_color_depth( 8 );
set_gfx_mode(GFX_AUTODETECT_WINDOWED, 800, 600, 0, 0);
set_palette(desktop_palette);

do_dialog(main_dialog, -1);

return 0;
}
END_OF_MAIN()