/*
Algorytm sprawdza, czy punkt p nalezy do wielokata W
Program zostal pobrany ze strony www.algorytm.org
Opracowal: Michal Knasiecki
--------------------------------------------------------
Uwaga:
Daje wejsciowe sa wczytywane z pliku dane.txt
Format zapisu danych wejsciowych znajduje sie w pliku !FormatDatych.txt
*/
#include <conio>
#include <stdio>
#include <stdlib>

//funkcja min
int min(int a, int b)
{
   if (a<b) return a;
   return b;
}
//funkcja max
int max(int a, int b)
{
   if (a>b) return a;
   return b;
}
//funkcja signum
int sign(int a)
{
   if (a == 0)
      return 0;
   if (a < 0)
      return -1;
   return 1;
}

struct vertex 			//Wierzcholek
{
int 		x,y;
};
vertex 	polygon[20];	//Tablica wierzcholow wielokata, max: 20
vertex 	p;				//Dany punkt p
vertex 	r;				//Drugi koniec odcinka |PR|
vertex 	tmp;
int 		n=0;			//Liczba wierzchalkow wielokata
int 		k;
//********************************************************
int przynaleznosc(vertex x, vertex y,vertex z)
{
int	det;
det=x.x*y.y+y.x*z.y+z.x*x.y-z.x*y.y-x.x*z.y-y.x*x.y;
if (det!=0) return(0); else
{
if ((min(x.x,y.x)<=z.x)&&(z.x<=max(x.x,y.x)) && (min(x.y,y.y)<=z.y)&&(z.y<=max(x.y,y.y)))
return(1);  else return(0);
};
};
int det(vertex x,vertex y,vertex z) //Wyznacznik macierzy kwadratowej stopnia 3.
{
return(x.x*y.y+y.x*z.y+z.x*x.y-z.x*y.y-x.x*z.y-y.x*x.y);
}
int przecinanie(vertex a,vertex b)
{
if ((przynaleznosc(p,r,a)==0)&&(przynaleznosc(p,r,b)==0))
{ //pólprosta nie przecina odcinka |AB| w koncach
if ((sign(det(p,r,a)) != sign(det(p,r,b))) &&
    (sign(det(a,b,p)) != sign(det(a,b,r)))) return(1); else return(0);
} else //do pólprostej nalezy przynajmniej jeden koniec odcinka |AB|
	{
   if ((przynaleznosc(p,r,a)==1)&&(przynaleznosc(p,r,b)==1))
   	{
      if ((sign(det(p,r,polygon[(k-1+n)%n])) == sign(det(p,r,polygon[(k+2)%n]))) &&
          (sign(det(p,r,polygon[(k-1+n)%n])) != 0)) return(0); else return(1);
      } else
      if ((przynaleznosc(p,r,polygon[(k-1+n)%n])==1)||(przynaleznosc(p,r,polygon[(k+2)%n])==1)) return(0);
       	else
      	{ //polprosta zawiera tylko wierzcholek
         	if (przynaleznosc(p,r,b)==1)
            	{
                  tmp=a;
                  return(0);
                }
                if (przynaleznosc(p,r,a)==1)
            	{
                  if ((sign(det(p,r,tmp)) == sign(det(p,r,b))) &&
                      (sign(det(p,r,tmp)) != 0)) return(0); else return(1);
                }
         }
   }
   return 0;
}
void oblicz(void)
{
int       l=0; //liczba przeciec
int       i;
div_t		 w;
//
for (i=0;i<n;i++)
{
   k=i;
   if (przynaleznosc(polygon[i], polygon[(i+1)%n], p) == 1)
   {
      printf("Punkt nalezy do krawedzi wielokata\n");
      printf("Dowlony klawisz...");
      return;
   }
   if (przecinanie(polygon[i],polygon[(i+1)%n])==1) l++;
}
printf("Rozwiazanie--------------\n");
printf("Liczba przeciec: %i\n",l);
w=div(l,2);
if (w.rem==0) printf("Punkt p NIE nalezy do wielokata\n"); else
printf("Punkt p nalezy do wielokata\n");
printf("Dowlony klawisz...");
}
void main(void)
{
FILE *plik;
int max_x=0;			//Najwieksza rzedna
int j=0;					//aktualny index tablicy wierzcholkow
//
clrscr();
printf("Dane wejsciowe:\n");
if ((plik=fopen("dane.txt","r"))==NULL)
	{
   printf("Plik \"dane.txt\" z danymi wejsciowymi nie istnieje\n");
   printf("Dowlony klawisz...");
   getch();
   } else
   {
   fscanf(plik,"%i",&p.x);
   fscanf(plik,"%i",&p.y);
   printf("Punkt p=(%i,%i)\n",p.x,p.y);
   do
   {
   fscanf(plik,"%i",&polygon[j].x);
   if (polygon[j].x>max_x) max_x=polygon[j].x;
   fscanf(plik,"%i",&polygon[j].y);
   j++;
   n=j;
   printf("Wierzcholek #%i=(%i,%i)\n",j,polygon[j-1].x,polygon[j-1].y);
   }
   while (!feof(plik));
   fclose(plik);
   //Wyznaczanie wspólrzednych drugiego konca odcinka
   r.x=max_x+1;
   r.y=p.y;
   //Punkt r na pewno znajduje sie poza wielokatem
   printf("Punkt r=(%i,%i)\n",r.x,r.y);
   oblicz();
   getch();
   }
}