#include	<stdlib.h>
#include	<stdio.h>
#include	<math.h>


#define	FUERA	0
#define	DENTRO	1
#define	POLIGONOS_TEST_MAX	4
#define	PUNTOS_TEST_MAX		5
#define	LINEAS_POR_POLIGONO	12


typedef struct{
	float X;
	float Y;
}Punto;

typedef struct{
	Punto P0, P1;
}Linea;

typedef struct{
	char nombre[5];
	int size;
	Linea lineas[LINEAS_POR_POLIGONO];
}Poligono;

const Poligono poligonos_test[POLIGONOS_TEST_MAX] = {
			{"Tria", 3, {
					{{0,0},{3,7}}, {{3,7},{6,0}}, {{6,0},{0,0}}, {{0,0},{0,0}},
					{{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
					{{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
				}
			},
			{"Rect", 4, {
					{{0,0},{0,7}}, {{0,7},{7,7}}, {{7,7},{7,0}}, {{7,0},{0,0}},
					{{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
					{{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
				}
			},
			{"Letr", 12, {
					{{0,0},{0,7}}, {{0,7},{1,7}}, {{1,7},{3,5}}, {{3,5},{5,7}},
					{{5,7},{6,7}}, {{6,7},{6,0}}, {{6,0},{5,0}}, {{5,0},{5,5}},
					{{5,5},{3,3}}, {{3,3},{1,5}}, {{1,5},{1,0}}, {{1,0},{0,0}}
				}
			},
			{"Cora", 12, {
					{{0,3},{0,5}}, {{0,5},{1,6}}, {{1,6},{2,6}}, {{2,6},{4,4}},
					{{4,4},{3,3}}, {{3,3},{2,4}}, {{2,4},{4,6}}, {{4,6},{5,6}},
					{{5,6},{6,5}}, {{6,5},{6,3}}, {{6,3},{3,0}}, {{3,0},{0,3}}
				}
			}
	};

const Punto puntos_test[PUNTOS_TEST_MAX] = {
		{0,0}, {3,4}, {2,6}, {3,6}, {4,6}
};

int algoritmo( const Poligono plgn, const Punto pnt ){
	//	Implementacion del algoritmo. Resultado = DENTRO/FUERA
	#define min(a,b)		((a<b)?a:b)
	#define max(a,b)		((a>b)?a:b)
	#define TOCA			( min(plgn.lineas[i].P0.Y,plgn.lineas[i].P1.Y) <= lineaH.P0.Y && lineaH.P0.Y <= max(plgn.lineas[i].P0.Y,plgn.lineas[i].P1.Y) )

	int resultado = 0;
	int i;
	int izq, drch;
	Punto cortes[LINEAS_POR_POLIGONO];
	Linea lineaH;
	
	// Traza una linea horizontal mas larga que el poligono a la altura del punto.
	lineaH.P0.X = pnt.X;
	lineaH.P0.Y = pnt.Y;
	lineaH.P1.X = pnt.X;
	lineaH.P1.Y = pnt.Y;
	for( i = 0 ; i < plgn.size ; i++ ){
		if( lineaH.P0.X	> plgn.lineas[i].P0.X ){
			lineaH.P0.X	= plgn.lineas[i].P0.X;
		}
		if( lineaH.P1.X	< plgn.lineas[i].P0.X ){
			lineaH.P1.X	= plgn.lineas[i].P0.X;
		}
	}
	lineaH.P0.X--;
	lineaH.P1.X++;

	// Comprueba todos los puntos de corte de con la linea trazada
	for( i = 0 ; i < plgn.size ; i++ ){
		if( TOCA ){
			float	xa = plgn.lineas[i].P0.X, 
					ya = plgn.lineas[i].P0.Y, 
					xb = plgn.lineas[i].P1.X, 
					yb = plgn.lineas[i].P1.Y;
			
			if( 0 != (xb-xa) ){
				float m, b;
				m = (yb-ya)/(xb-xa);
				b = ((ya*xb)-(yb*xa))/(xb-xa); 
				
				if( 0 != m ){
					cortes[i].X = (lineaH.P0.Y-b)/m;
					cortes[i].Y = lineaH.P0.Y;
				}else{
					// La linea plgn.lineas[i] es horizontal.
					cortes[i].X = pnt.X;
					cortes[i].Y = lineaH.P0.Y;
				}
			}else{
				// La linea plgn.lineas[i] es vertical.
				cortes[i].X = plgn.lineas[i].P0.X;
				cortes[i].Y = lineaH.P0.Y;
			}
		}else{
			cortes[i].X = pnt.X;
			cortes[i].Y = pnt.Y+1; // Punto de corte NO valido. No afecta al resultado
		}
		
		if( cortes[i].X == plgn.lineas[i].P1.X && cortes[i].Y == plgn.lineas[i].P1.Y ){
			if( (plgn.lineas[i].P0.Y < lineaH.P0.Y && plgn.lineas[(i+1)%plgn.size].P1.Y > lineaH.P1.Y)
				|| (plgn.lineas[i].P0.Y > lineaH.P0.Y && plgn.lineas[(i+1)%plgn.size].P1.Y < lineaH.P1.Y) ){
				i++;
				cortes[i].X = pnt.X;
				cortes[i].Y = pnt.Y+1;
			}
		}
	}
	
	// Cuenta los puntos de corte a la izq y a la drch del punto
	for( i = 0, izq = 0, drch = 0 ; i < plgn.size ; i++ ){
		if( cortes[i].Y == pnt.Y ){
			if( cortes[i].X < pnt.X ){
				izq++;
			}
			if( cortes[i].X > pnt.X ){
				drch++;
			}
		}
	}
	
	// Si hay numero impar de cortes a algun lado del punto, este se encuentra dentro.
	if( izq%2 || drch%2 ){
		resultado = DENTRO;
	}else{
		resultado = FUERA;
	}
	

	return resultado;
}

int main(){

	int i, j;

	printf("www.TODOPIC.com.ar\n");
	printf("Concurso de programacion en C.\n");
	printf("Nombre del concursante: Jose Antonio Garcia Peiro");

	for( i = 0 ; i < POLIGONOS_TEST_MAX ; i++ ){

		printf( "\n\nTest del poligono %s...", poligonos_test[i].nombre );

		for( j = 0 ; j < PUNTOS_TEST_MAX ; j++ ){

			if( DENTRO == algoritmo( poligonos_test[i], puntos_test[j] ) )
				printf( "\nEl punto { %2.1f, %2.1f } se encuentra DENTRO", (double)puntos_test[j].X, (double)puntos_test[j].Y );
			else
				printf( "\nEl punto { %2.1f, %2.1f } se encuentra FUERA", (double)puntos_test[j].X, (double)puntos_test[j].Y );

		}
	}

	printf("\n\nTest terminado.");
	return 0;
}