#include<stdlib.h>
#include<stdio.h>
# define SQR(x) ((x)*(x))

/******************************************************************************/
/* Ważna dla Ciebie struktury                                                                                           */
/******************************************************************************/

typedef struct {
    int x,y;
    int otoczka; /* wartosc zero oznacza, że punkt leży wewnątrz otoczki, 1 - nie wiadomo */
    } punkt;

/* struktura zawierająca punkty  (tablica wskaźników punktów i ich ilość) */

typedef struct {
    int ilosc_punktow;
    punkt **punkty;  /* tablica (wskaźników do) punktów na płaszczyźnie */
} punkty;

punkty tab_pt; /* ta struktura może być kopcem */

typedef struct el* welement;
typedef struct el{
  punkt *p;
  welement next;  
} element;

welement stos;
int ile2;
int numer_pomnika=0;
int pomnik_x,pomnik_y;
int tak;
/*******************************************************************************/

int dane_z_pliku(int argc, char *argv[]);

void wypisz_stos(void);

void graham();

/******************************************************************************/
/*Funkcja main                                                                                                                */
/******************************************************************************/

main(int argc, char *argv[])
{
    FILE* dane;
    int ile1,ile2,i;
    
	if (argc==2) dane=fopen(argv[1],"r"); else dane=fopen("graham_dane.txt","r");
	fscanf(dane,"%d",&ile1);
	fscanf(dane,"%d",&ile2);
	close(dane);
	
    for(i=0;i<ile2;i++){
      dane_z_pliku(argc,argv);
      graham();  
      wypisz_stos();
      //getchar();
      numer_pomnika++;
  }
  getch();            
  return 0;
}
/***************************************************************************/
/*     Definicje funkcji                                                                                                   */
/***************************************************************************/

/* Funkcje wczytujące dane z pliku */
int dane_z_pliku(int argc, char *argv[]){

	int i=0; /* ilosc wczytanych punktów */
	FILE* dane;
	punkt **pty;
	punkt **pomniki;
	punkt **kopia;
	int ilosc_punktow,ilosc;
    int ile1; //pkt
    int ile2; //pomniki
	if (argc==2) dane=fopen(argv[1],"r"); else dane=fopen("graham_dane.txt","r");
	//printf("Wczytuje dane\n");
	fscanf(dane,"%d",&ile1);
	fscanf(dane,"%d",&ile2);
	ilosc=ile1+ile2;
	ilosc_punktow=ile1+1;

	pty=(punkt**)malloc(ile1*sizeof(punkt*));
	pomniki=(punkt**)malloc(ile2*sizeof(punkt*));
	kopia=(punkt**)malloc(ilosc*sizeof(punkt*));
	int c;
	punkt *pt;
	while((c=getc(dane))!=EOF){
		ungetc(c,dane);
		pt=(punkt *)malloc(sizeof(punkt));
		fscanf(dane,"%d",&(pt->x));
		fscanf(dane,"%d\n",&(pt->y));
		pt->otoczka=1;
		if(i<ile1){
                    kopia[i]=pt;
                    //printf("do dane robocze: (%d,%d) przed pomnikiem \n",pt->x,pt->y);
        }
        if(i==numer_pomnika+ile1){
                    //printf("do dane robocze: (%d,%d) pomnik \n",pt->x,pt->y);
                    kopia[ile1]=pt;
                    pomnik_x=pt->x;
                    pomnik_y=pt->y;
        }
	    i++;
    }
    pty=kopia;
	
    tab_pt.ilosc_punktow=ilosc_punktow;
    tab_pt.punkty=pty;
	//printf("Dane zostaly wczytane\n");

	close(dane);
 	return 0;
}

/******************************************************************************/
/* Ważna dla Ciebie funkcja                                                                                             */
/******************************************************************************/
int porownaj1(punkt *p, punkt *p1, punkt *p2)
/* funkcja porównująca położenie punktów p1 i p2, p to punkt odniesienia, funkcja porównuje na podstawie kąta */
{ 
  int wyznacznik;
  wyznacznik=(p1->x-p->x)*(p2->y-p->y)-(p1->y-p->y)*(p2->x-p->x);

  return wyznacznik;
}
/*******************************************************************************/

int porownaj2(punkt *p, punkt *p1, punkt *p2)
/* funkcja porównująca położenie punktów p1 i p2, p to punkt odniesienia, funkcja porównuje na podstawie odległości */
{
    if (SQR(p1->x-p->x)+SQR(p1->y-p->y)>SQR(p2->x-p->x)+SQR(p2->y-p->y)) return 1;
    else  if (SQR(p1->x-p->x)+SQR(p1->y-p->y) == SQR(p2->x-p->x)+SQR(p2->y-p->y)) return 0;
    else return -1;
}

int porownaj(punkt *p, punkt *p1, punkt *p2)
{
    if (porownaj1(p,p1,p2)>0) return 1;
    else if (porownaj1(p,p1,p2)<0) return -1;
    else if (porownaj2(p,p1,p2)>0) { p2->otoczka=0; return 1;}
    else if (porownaj1(p,p1,p2)<0) { p1->otoczka=0; return -1;}
}

/* zamiana dwóch punktów  */
void swap(punkt **a,punkt **b)
{
  punkt *tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}

/* funkcja wyznaczająca punkt p0 */
int findp0(punkty *a)
{
  int i;
  int p0=0;
  for(i=1;i< a->ilosc_punktow;i++)
    {

      if(a->punkty[i]->y< a->punkty[p0]->y) p0=i;
      else if(a->punkty[i]->y==a->punkty[p0]->y)  if(a->punkty[i]->x<a->punkty[p0]->x) p0=i;
    }
  return p0;
}

void heapify(punkty *a, int gdzie)
{
  int left,right,largest;
  
  if( (left=2*gdzie) <a->ilosc_punktow && (porownaj(a->punkty[0],a->punkty[left],a->punkty[gdzie])<0)) largest=left; else largest=gdzie;
  if( (right=2*gdzie+1) <a->ilosc_punktow && (porownaj(a->punkty[0],a->punkty[right],a->punkty[largest])<0)) largest=right;
  
  if(largest!=gdzie)  {swap(a->punkty+gdzie,a->punkty+largest); heapify(a,largest);}

}

void buildheap(punkty *a)
{
  int i;
  for(i=(a->ilosc_punktow-1)/2;i>0;i--) heapify(a,i);
}

void printtab(punkty *a)
{
  int i;

  for(i=0;i<a->ilosc_punktow;i++) printf("(%d,%d) ",a->punkty[i]->x,a->punkty[i]->y);
  printf("\n");
} 

void heapsort(punkty *a)
{
  int s;
  s=a->ilosc_punktow;

  int p0;
  p0=findp0(a);
  swap(a->punkty,a->punkty+p0);

  buildheap(a);
  a->ilosc_punktow--;
  while(a->ilosc_punktow>1)
    {
      swap(a->punkty+1,a->punkty+a->ilosc_punktow);
      heapify(a,1);
	a->ilosc_punktow--;
    }
  a->ilosc_punktow=s;
}


void inicjuj(void){ stos=NULL; }

void pop(void)
{
  welement tmp;
  tmp=stos;
  if (stos==NULL){ printf("Blad: pusty stos\n"); exit(-1);}
  stos=stos->next;
  free(tmp);
}

void push(punkt *p)
{
  welement tmp;

  tmp=(welement)malloc(sizeof(element));
  tmp->p=p;
  tmp->next=stos;
  stos=tmp;
}

punkt * top()
{
  if (stos!=NULL) return stos->p;
}

punkt * next_to_top()
{
  if (stos!=NULL) if (stos->next!=NULL) return stos->next->p;
}

void wypisz_stos(void)
{
  welement tmp;
  tmp=stos;
  if (stos==NULL){ printf("Blad: pusty stos\n"); exit(-1);}
  while(tmp!=NULL)
    {
      //printf("(%d,%d) ",tmp->p->x,tmp->p->y);
      if((tmp->p->x)==pomnik_x){
                                if((tmp->p->y)==pomnik_y) tak=1;
      }
      tmp=tmp->next;
    }
  if (tak==1) printf("TAK \n"); else printf("NIE \n");
  tak=0;
}

/***********************************************************/
/* To masz napisać                                                                         */
/***********************************************************/
int brak_skretu(punkt *p, punkt *p1, punkt *p2)
{ 
  if(porownaj1(p,p1,p2)>0) return 0; else return 1;
}

void graham()
{
  
  int i=1;
  inicjuj(); //inicjuje pusty stos
    //getch();
  heapsort(&tab_pt);
  push(tab_pt.punkty[0]);
  while(tab_pt.punkty[i]->otoczka==0) i++;
  push(tab_pt.punkty[i++]);
  while(tab_pt.punkty[i]->otoczka==0) i++;
  push(tab_pt.punkty[i++]);
  
  for(i; i<tab_pt.ilosc_punktow; i++){
                                      if(tab_pt.punkty[i]->otoczka){
                                                                     //while(brak_skretu(next_to_top(), top(), tab_pt.punkty[i])) pop();
                                                                     push(tab_pt.punkty[i]);
                                                                     }
                                      }
}