/**
 * Algorytm sprawdza, czy punkt p nalezy do wielokata W
 * Program zostal pobrany ze strony www.algorytm.org
 * (c)2005 Tomasz Lubinski
 */

public class Polygon {

	private static int n=0;			//Liczba wierzchalkow wielokata
	private static int polygonx[];
	private static int polygony[];
	private static int rx, ry;		//wspolrzedne pomocnicze
	private static int tmpx, tmpy;  //wspolrzedne pomocnicze	
	private static int px, py;		//wspolrzedne punktu
	private static int k;	
	
	private static int przynaleznosc(int xx, int xy, int yx, int yy, int zx, int zy) {
		int	det = xx*yy + yx*zy + zx*xy - zx*yy - xx*zy - yx*xy;
		if (det!=0) 
			return 0; 
		else {
			if ((Math.min(xx, yx) <= zx) && (zx <= Math.max(xx, yx)) &&
				(Math.min(xy, yy) <= zy) && (zy <= Math.max(xy, yy)))
				return 1;
			else
				return 0;
		}
	}
	
	 //Wyznacznik macierzy kwadratowej stopnia 3.
	private static int det(int xx, int xy, int yx, int yy, int zx, int zy) {
		return (xx*yy + yx*zy + zx*xy - zx*yy - xx*zy - yx*xy);
	}
	
	private static int przecinanie(int ax, int ay, int bx, int by) {
		if ((przynaleznosc(px, py, rx, ry, ax, ay) == 0) && 
			(przynaleznosc(px, py, rx, ry, bx, by) == 0))	{ 
			//pólprosta nie przecina odcinka |AB| w koncach
			if ((Math.signum(det(px, py, rx, ry, ax, ay)) != Math.signum(det(px, py, rx, ry, bx, by))) &&
				(Math.signum(det(ax, ay, bx, by, px, py)) != Math.signum(det(ax, ay, bx, by, rx, ry))))
				return 1;
			else
				return 0;
			}
		else {
//			do pólprostej nalezy przynajmniej jeden koniec odcinka |AB|
			if ((przynaleznosc(px, py, rx, ry, ax, ay) == 1) && 
				(przynaleznosc(px, py, rx, ry, bx, by)==1))	{
	      		if (Math.signum(det(px, py, rx, ry, polygonx[(k-1+n)%n], polygony[(k-1+n)%n])) == Math.signum(det(px, py, rx, ry, polygonx[(k+2)%n], polygony[(k+2)%n])) &&
      				Math.signum(det(px, py, rx, ry, polygonx[(k-1+n)%n], polygony[(k-1+n)%n])) != 0)
	      			return 0;
	      		else
	      			return 1;
	      } else {
	      	if ((przynaleznosc(px, py, rx, ry, polygonx[(k-1+n)%n], polygony[(k-1+n)%n]) == 1) || 
	      		(przynaleznosc(px, py, rx, ry, polygonx[(k+2)%n], polygony[(k+2)%n]) == 1))
	      		return 0;
	       	else {
	       		//polprosta zawiera tylko wierzcholek
	         	if (przynaleznosc(px, py, rx, ry, bx, by) == 1) {
	                  tmpx = ax;
	                  tmpy = ay;
	                  return 0;
	         	}
	            if (przynaleznosc(px, py, rx, ry, ax, ay)==1){
	            	if (Math.signum(det(px, py, rx, ry, tmpx, tmpy)) == Math.signum(det(px, py, rx, ry, bx, by)) &&
	            		Math.signum(det(px, py, rx, ry, tmpx, tmpy)) != 0) 
	            		return 0;
	            	else
	            		return 1;
	            }
	         }
	      }
	   }
		return 0;
	}


	
	private static void oblicz() {
		
		int l=0; //liczba przeciec
		int i;
		
		for (i=0; i<n; i++) {
			k=i;
			if (przynaleznosc(polygonx[i], polygony[i], polygonx[(i+1)%n], polygony[(i+1)%n], px, py) ==1) {
				System.out.println("Punkt nalezy do krawedzi wielokata");
				return;
			}
			if (przecinanie(polygonx[i], polygony[i], polygonx[(i+1)%n], polygony[(i+1)%n]) == 1)
				l++;
	   }
		System.out.println("Rozwiazanie--------------");
		System.out.println("Liczba przeciec: " + l);
		if ((l % 2) == 0) 
			System.out.println("Punkt p NIE nalezy do wielokata\n"); 
		else
			System.out.println("Punkt p nalezy do wielokata\n");
	} 

	public static void main(String[] args) {
		
		int max_x = Integer.MIN_VALUE;		//Najwieksza rzedna
		
		System.out.println("Dane wejsciowe:");
		
		System.out.println("Podaj wspolrzedne punktu:");
		px = Console.readInt("x=");
		py = Console.readInt("y=");
		
		System.out.println("Podaj liczbe punktow tworzacych wielokat:");
		n = Console.readInt("n=");
		polygonx = new int[n];
		polygony = new int[n];
		
		for (int i=0; i<n; i++){
			System.out.println("Punkt " + (i+1));
			polygonx[i] = Console.readInt("x=");
			polygony[i] = Console.readInt("y=");
			if (polygonx[i] > max_x) 
				max_x = polygonx[i];
		}
		
	   //Wyznaczanie wspólrzednych drugiego konca odcinka
	   rx = max_x+1;
	   ry = py;
	   
	   //Punkt r na pewno znajduje sie poza wielokatem
	   System.out.println("Punkt r=("  + rx + ", " + ry + ")");
	   oblicz();
	 }
}