Algoritmos y Demas

Hoy entre de nuevo a Topcoder, el SRM 565 con un poco de emoción y recelo debido a que no eh entrado a un concursos tipo Topcoder desde ya hace 11 meses, y como era de esperarse me fue muy mal, sacando 0 puntos.
En los próximos meses pretendo entrenar a alumnos para los Regionales de ACM y debo ponerme a practicar aun que sea en CodeForces y Topcoder, también debo hacer la misma tarea que ellos hacen, cada problema que no podamos resolverlo en el concurso tratarlo de sacar de tarea y aquí voy a explicar algunos de ellos como se resuelven.

Empecemos, este el problema:

Resumiendo el problema: tienes que crear un método llamado minimumPrice que reciba dos arreglos long[] dread y int[] Price , tu tienes que pasar por una serie de mostro en el orden establecido , cada mostro es sobornable y por lo tanto puedes pagar un precio ( que va de 1 a 2 ) , si lo pagas el mostro te apoyara con los siguientes mostros, si no lo pagas el te atacar si y solo si su temor ( que es igual a su valentía ) es mayor que la suma de todos los mostros que se hallan comprado.

Tu tarea es calcular el mínimo precio para pasar por todos los mostros sin ser atacado.

Con esta información se puede plantear una dinámica muy sencilla de posición x temor , el numero de mostros es menor a 50 , pero el temor esta entre 1 y 10^12, lo cual arruina completamente esta dinámica simple.

Pase varios minutos sin encontrar una manera de resolver el problema de manera optima con una programación dinámica, por lo tanto hice un glotón que sospechaba fuertemente no era suficiente para resolver todos los casos de prueba y así fue.

Revisando soluciones de otros programadores y viendo como lo resolvieron, la programación dinámica era correcta, solo que en vez de tomar la posición y la bravura, era la posición y el precio guardando la suma de todos los miedos ( me recordó a una película no se por que) o mejor dicho maximizando la suma de todos los mostros sobornados con un costo especifico, y de ahí basarnos para calcular si el siguiente mostro se puede sobornar o se puede pasar derecho con cierta cantidad de dinero, si no se puediera se marcaria con -1 o con algún valor para determinar con ese costo no se pudo superar ese mostro.

Veamos el código:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class MonstersValley {
public:
	int minimumPrice(vector <long long>, vector <int>);
};

long long din[51][101];

int MonstersValley::minimumPrice(vector<long long> dread, vector <int> price) {
	memset(din, -1, sizeof( din )); // marcamos como imposible todas las posiciones
	din[0][price[0]] = dread[ 0 ]; // la unica manera de pasar al primero mostro es sobornandolo
	for( int currentMonster = 1; currentMonster < dread.size() ; currentMonster++ ){
	    for( int cost = 0; cost <= dread.size() * 2  ; cost++)
	      if(din[currentMonster - 1][ cost] >= 0 ){
	          if( din[currentMonster -1][ cost] >= dread[ currentMonster ] )
	               din[currentMonster][cost ]  = max(din[currentMonster][cost ] , din[currentMonster-1][cost ] );
	          din[currentMonster][cost +price[currentMonster]]  =
	                 max(din[currentMonster][cost + price[currentMonster]] , 
	                     din[currentMonster-1][cost ]  + dread[currentMonster]);
	      }
	}
	for(int cost = 0; cost <= dread.size() * 2 ; cost++ ){
	    if(din[dread.size() - 1 ][ cost ] >= 0 ) return cost;
	}
	return -1;
}


//Powered by [KawigiEdit] 2.0!

Felicidades a todos los que participaron en el final de la Universidad Politecnica de Tlaxcala, aqui les dejo la solucion de los problemas

Problema A: Palabras
En este problema solo hay que ver si una cadena se puede formar con las letras de otra cadena

# include <stdio.h>
# include <string.h>

# define MAX 1000000

char wordA[MAX + 1], wordB[MAX+1];
int hash[256];

main(){
  int x;
  while( scanf("%s %s", wordA, wordB) != EOF ){
  	memset( hash, 0, sizeof( hash ));
  	for( x = 0; x < strlen(wordA); x++)
  	  hash[ wordA[x] ]++;
  	for( x = 0; x < strlen(wordB); x++)
  	  hash[ wordB[x] ]--;
  	 for( x = 0; x < 256 ; x++) if( hash[ x ] < 0 ) break;
  	 printf("%s\n", ( x < 256) ? "NO" : "YES");
  }
  return 0;	
}

Problema B: El señor de los anillos
Señor de los anillos, un problema que es definitivamente un dijkstra, lo complicado de este dijkstra es ver que nodos estan vistos por Sauron, como pueden ver las recurrencias son para los nodos que Sauron ve los nodos es de 1 a 7, de esa menera si sacamos el LCM de todos estos numeros tenemos esto (2*2*3*5*7) este es el modulo que necesitamos para saber si se repite sobre cualquier nodo, si nosotros ya calculamos el nodo X con el modulo Y, entonces ya no hay que evaluarlo de nuevo.

# include <stdio.h>
# include <string.h>

# define MOD (2*2*3*5*7)
# define MAX 102

int periodo[MAX+1];
int graph[MAX+1][MAX+1] , vis[MAX+1][MAX+1];

int distance[ MAX + 1 ][ MOD + 2];

main(){
  int n, m, dis, node, mod, x, y, a, b, nextnode;
  while( scanf("%d %d", &n, &m) != EOF && ( n || m )) {
     for( x = 1; x <= n; x++) scanf("%d", &periodo[ x ]);
     periodo[ 0 ] = MOD + 1;
     memset( graph, 0, sizeof( graph ));
     for( x = 0; x < m; x++){
       scanf("%d %d", &a, &b);
       graph[a][b] = graph[b][a] = 1;
     }
     for( x = 0; x <= n; x++) graph[x][x] = 1;
     for( node = 0; node <= n; node++)
     for( mod = 0; mod <= MOD; mod++){
       vis[ node ][ mod ] = 0;
       distance[ node ][ mod ] = (1<<30);	
     }
     node = 0;
     mod = 0;
     distance[ node ][ mod ] = 0;
     while( node != -1){
       dis = distance[ node ][ mod ];
       vis[node][ mod ] = 1;
       if( node == n ) break;
       for( nextnode = 0; nextnode <= n; nextnode++ ) if( graph[node][nextnode] == 1){
       	 if( distance[nextnode][ (mod + 1 ) % MOD ] > dis + 1 && (mod + 1) % periodo[ nextnode ] != 0 ){
       	   	distance[ nextnode ][ ( mod + 1 ) % MOD ] = dis + 1;
       	 }
       }
       node = -1;
       dis = (1<<30);
       for( x = 0; x <= n; x++)
         for( y = 0; y <= MOD; y++) if(vis[x][y] == 0 && distance[x][y] < dis){
            dis = distance[x][y];
            node = x;
            mod = y;
         }
     }
     printf("%d\n", ( node == -1 ) ? -1 : dis );
  }
  return 0;	
}

Problema C: Dados
Es un problema de conteo, ver de cuantas maneras distintas puedo colocar los dados para que me salga la suma solicitada, se puede hacer con un programacion dinamica o bien con un backtraking, que serviria de la misma manera, o bien cuatro fors con bastantes ifs.

# include <stdio.h>
# include <string.h>

# define MAX 5
# define MAX_CARAS 40
# define MAX_SUMA 100

int dados[MAX+1][MAX_CARAS+1];
int ndados[MAX+1];
int din[MAX+1][MAX_SUMA+1], S, n;

int solve(int position, int suma){
  int res = 0, x;
  if( suma > S ) return 0;
  if( position == n ) return S == suma ? 1 : 0;
  if( din[position][suma] != -1) return din[position][suma];
  for( x = 0; x < ndados[ position ]; x++)
    res += solve( position + 1, suma + dados[ position ][ x ]);
  return din[position][suma] = res;
}

main(){
  int  x, y, prod,  a , b;
  while( scanf("%d %d", &n, &S) != EOF && ( n || S)){
     prod = 1; 
     for( x = 0; x < n; x++){
       scanf("%d", &ndados[ x ]);	
       for(y = 0; y < ndados[ x ]; y++){
       	 scanf("%d", &dados[x][y]);
       }
       prod *= ndados[x];
     }	
     memset( din, -1, sizeof( din ));
     a = solve(0, 0);
     b = prod;
     if( a == b ) printf("1\n");
     else if( a == 0 ) printf("0\n");
     else printf("%d/%d\n", a , b);
  }
  return 0;
}

Problema D: Palíndromo
Se puede hacer con una programacion dinamica para que sea rapido o bien cuatro fors ya que el tamaño de la cadena es pequeña y saldria a tiempo.

# include <stdio.h>
# include <string.h>

# define MAX 100

int din[MAX+1][MAX+1];
char word[MAX+1];

int ispalindrome(int a, int b){
  if( a >= b) return 1;
  if(word[a] != word[b]) return 0;
  if( din[a][b] != -1) return din[a][b];
  return din[a][b] = ispalindrome( a + 1, b - 1);
}

main(){
  int a, b, n, cont;
  while( scanf("%s", word) != EOF ){
     memset( din, -1, sizeof( din ));
     n = strlen(word);
     cont = 0;
     for( a = 0; a < n; a++)
     for( b = a; b < n; b++)
       cont += ispalindrome(a, b );
     printf("%d\n", cont);
  }
  return 0;	
}

Problema E: Buscando Cuadrados
El problema de encontrar una submatrix sobre otras, en especifico sobre este problema como las matrices son pequeñas, entonces podemos hacer fuerza bruta, y con cuatro fors comparar si la matriz A esta en todas las posiciones iniciales que podamos colocarle en la matriz B, si queremos optimizarlo tendriamos que meternos un poco con el KMP, para poder hacer un conteo rapido.

# include <string.h>
# include <stdio.h>

# define MAX 100

char map[MAX+1][MAX+1], submap[MAX+1][MAX+1];

main(){
  int n, size, row, col, r, c, cont, query, q;
  while( scanf("%d", &n) != EOF && n ){
     for( row = 0; row < n; row++) scanf("%s", map[row]);
     scanf("%d", &query);
     for( q = 0; q < query ; q++){
        scanf("%d", &size);	
        cont = 0;
        for( row = 0; row < size ; row++) scanf("%s", submap[row]);
        for( row = 0 ; row < n; row++)
        for( col = 0 ; col < n; col++){
           for( r = 0; r < size && r + row < n ; r++){
             for( c = 0; c < size && c + col < n ; c++) 
               if( map[row+r][col+c] != submap[r][c]) break;
             if( c < size ) break;	
           }
           if( r >= size ) cont++;
        }
        printf("%d\n", cont);
     }
  }
  return 0;	
}

Problema F: Molde!
El problema nos indica que debemos hacer un convex hull, posteriomente sacar el perimetro y el area del convex encontrado.

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

# define MAX 100000

typedef struct { int x, y; } Point;

Point Poligono[MAX+1];
Point convex[MAX+1];
int vis[MAX+1];

int n;

double valumen, perimetro;

double abso( double a ){ return a < 0.0 ? -a : a; }

long long cross_product(Point a, Point b, Point c){
   return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

long long cross(Point A, Point B, Point C){
  Point AB;
  Point AC;
  AB.x = B.x-A.x;
  AB.y = B.y-A.y;
  AC.x = C.x-A.x;
  AC.y = C.y-A.y;
  return AB.x * AC.y - AB.y * AC.x;
}

double area2D_Polygon( int n, Point* V ) {
    double area = 0;
    int  i, j, k;   
    if (n < 3) return 0; 
    for (i=1, j=2, k=0; i<n; i++, j++, k++) {
        area += V[i].x * (V[j].y - V[k].y);
    }
    area += V[n].x * (V[1].y - V[n-1].y); 
    return abso(area / 2.0);
}

double distance( Point a, Point b ){
  return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) ) ;	
}


double solve( int n ){
   Point p, ptmp, pposible;
   int nconvex = 0, x, pos, posa, post;
   double area;
   memset( vis, 0, sizeof( vis ));
   if( n == 1) return 0;
   if( n == 2) return distance( Poligono[0], Poligono[1]) * 2.0;
   p = Poligono[0];
   pos = 0;
   for( x = 1; x < n; x++){
   	  if(p.x > Poligono[x].x || (p.x == Poligono[x].x && p.y > Poligono[x].y)){
   	     p = Poligono[x];
   	     pos = x;
   	  }
   }
   posa = pos;
   while( 1 ){
      vis[pos] = 1;	
      convex[nconvex++] = p;
      posa = pos;
      for(x = 0; x < n; x++){
      	if( vis[x] == 0){
      	   pos = x;
      	   break;	
      	}
      }
      for( x = x + 1; x < n; x++){
          if( cross( Poligono[posa],Poligono[x], Poligono[pos]) < 0 ){
         	pos = x;
         }else if(cross( Poligono[posa],Poligono[x], Poligono[pos])  == 0 && distance( Poligono[posa] , Poligono[ pos ])
         	       < distance( Poligono[posa] , Poligono[ x ])){
         	   pos = x;	
         }
      }
      p = Poligono[ pos ];
      if( vis[ pos ] == 1) break;
   }
   perimetro = 0.0;
   convex[ nconvex] = convex[ 0 ];
   for( x = 0; x < nconvex; x++) perimetro += distance( convex[ x ], convex[ (x + 1) % nconvex]);
   area =  area2D_Polygon( nconvex, convex);
   printf("%.2lf %.2lf %.2lf\n", perimetro, area, valumen / area);
}


main(){
  int x;
  while( scanf("%d %lf", &n, &valumen) != EOF && ( n != 0 || valumen != 0 )){
     for( x = 0; x < n; x++) scanf("%d %d", &Poligono[ x ].x, &Poligono[ x ].y);	
     solve( n );
  }
  return 0;	
}

Cualquier sugerencia, explicacion mas detallada, favor de enviarme un correo a rodrigo.burgos@gmail.com

Concurso Semifinal UTP

Felicidades a todos, por participar en este tipo de competicion, si quieren ver los problemas y resultados puede verlos en el blog oficial http://concursodeprogramacionupt.wordpress.com/ aqui les dejo los codigos de cada uno de los problemas espero les gusten.

Problema A:

El problema A se tenia que saber cual es el alumno con la coordenada Y mas cercana a 0, el unico truco seria ver que tambien puede ser negativo el valor.

# include <stdio.h>
# include <string.h>
# define MAX 100

typedef struct { char nombre[1000];  int X, Y; } CONTESTANT;

CONTESTANT contestant[ MAX + 1];

int abso( int a ){ return a < 0 ? -a : a; }

main(){
  int ncases , cases, ncontestant, closer, cntResponse, x;
  for( scanf("%d", &ncases), cases = 1 ; cases <= ncases ; cases++ ) {
  	scanf("%d", &ncontestant);
  	closer = (1<<30);
  	for( x = 0; x < ncontestant; x++){
  	   	scanf("%s %d %d", contestant[ x ].nombre, &contestant[ x ].X, &contestant[ x ].Y );
  	   	if( closer > abso( contestant[x].Y ) ){
  	   	  closer = abso( contestant[x].Y );
  	   	}
  	}
  	cntResponse = 0;
  	for( x = 0; x < ncontestant ; x++ ){
  	  if( closer == abso( contestant[x].Y)) {
  	    if( cntResponse != 0 ) printf(" ");
  	    printf("%s", contestant[x].nombre );
  	    cntResponse++;
  	  }	
  	}
  	printf("\n");
  }
  return 0;	
}

Problema B:

Un problema un poco dificil para aquellos que empiezan en esto de la programacion , pero necesario en cualquier concurso, son los problemas de programacion dinamica, este un poquito dificil ya que requeria programación dinamica mas mascara de bits

# include <stdio.h>
# include <string.h>

int n;
char map[6][1002];
int din[1<<6][1002];
int block[2][6];

int min( int a, int b ){ return a < b ? a : b; }

int contbits( int mask ){ return mask == 0 ? 0 : contbits( mask >> 1 ) + ( mask & 1); }

int solve(int r, int c, int dr, int dc, int position){
    int res = (1<<22), cst;
	if( r >= 5 || r < 0 || c >= 2 ) return (1<<22);
	if( r == dr && c == dc ) return map[r][position] - '0';
   	if( block[c][r] == 1 || block[c][r] == 2 || block[c][r] == 10) return (1<<22);
   	block[c][r] = 10;
   	cst = (map[r][position] == '@') ? 0 : map[r][position]-'0';
   	res = min( res, solve( r+1, c, dr , dc, position )+ cst);
   	res = min( res, solve( r-1, c, dr , dc, position )+ cst);
   	res = min( res, solve( r, c+1, dr , dc, position+1 )+ cst);
   	block[c][r] = 0;
   	return res;
}

int mark( int r, int c, int dr, int dc, int position, int rt, int aspectedResult){
	int cst;
	if( r >= 5 || r < 0 || c >= 2 || rt > aspectedResult) return 0;
	if( r == dr && c == dc ){
	   if( aspectedResult == rt + map[r][position] - '0'){
 	     block[c][r] = 1;
	     return 1;	
	   }
	   return 0;
	}
	if( block[c][r] == 1 || block[c][r] == 2 || block[c][r] == 10) return 0;
	block[c][r] = 10;
	cst = map[r][position] == '@' ? 0 : map[r][position]-'0';
	if( mark( r+1, c, dr , dc, position, cst + rt, aspectedResult ) ){
	  block[c][r] = 1;
	  return 1;	
	}
   	 if( mark( r-1, c, dr , dc, position, cst + rt, aspectedResult  )){
	  block[c][r] = 1;
	  return 1;	
	}
   	 if( mark( r, c+1, dr , dc, position+1, cst + rt, aspectedResult )){
	  block[c][r] = 1;
	  return 1;	
	}
	block[c][r] = 0;
	return 0;
}

int cost( int position, int mask, int newmask ){
  int x, last, y, a, b;
  int r = 0, rt;
   memset( block, 0, sizeof( block ));
   if( position != 0 ) for( x = 0; x < 5; x++) block[0][x] = 1;
   for( x = 0 ; x < 5; x++) if( ( mask & (1<<x) )   > 0 ) block[0][x] = 2;
   for( x = 0 ; x < 5; x++) if( ( newmask & (1<<x) )   > 0 ) block[1][x] = 2;
   last = 0;
   for( x = 0 ; x < 5; x++) 
     if( ( mask & (1<<x) )   > 0 ) {
        for( y = last ; y < 5; y++) if( ( newmask & (1<<y) )   > 0 ){
        	block[0][x] = 0;
        	block[1][y] = 0;
        	rt = solve(x, 0, y, 1, position);
        	if( rt < (1<<22)){
        	  mark( x, 0, y, 1, position, 0, rt);
        	  r += (rt - ( map[x][position] == '@' ? 0: map[x][position] -'0'));
        	} else r = rt;
        	last = y+1;
        	block[0][x] = 2;
        	block[1][y] = 2;
        	break;
        }
     }
   return r;
}

int alfalfasMoves( int mask, int position ){
  int newmask, cst, tmp;
  int res = (1<<22);
  if( position >= n -1 ) return 0;
  if(din[mask][position] !=-1) return din[mask][position];
  for(newmask = 0; newmask < (1<<5) ; newmask++) if( contbits( newmask) == 3){
  	cst =  cost( position, mask, newmask ) ;
  	if( cst < (1<<22)){
  		cst += alfalfasMoves( newmask, position + 1);
  		if( cst < res ){
  			tmp = newmask;
  	  		res = min( res, cst ) ;
  		}
  	}
  }  
  return din[mask][position] = res;
}

main(){
  int r, mask, x;
  while( scanf("%d", &n ) != EOF && n ) {
    for( x = 0; x < 5; x++) scanf("%s", map[ x ]);
    mask = 0;
    for( x = 0 ; x < 5; x++) 
      if( map[x][0] == '@' ){
        mask |= (1<<x);	
      }
    memset( din, -1, sizeof( din ));
    r =  alfalfasMoves(mask, 0);
    printf("%d Jijuan%s\n", r , (r == 1 ? "" : "s")); 
  }
  return 0;	
}

Problema C:

Es un problema de busqueda en profundidad, o amplitud, aun que es mas secillo programar la profunidad marcando en la matriz VIS los lugares a dondes puede ir Diego.

# include <stdio.h>
# include <string.h>

# define MAX 100

char map[MAX+1][MAX+1];
int vis[MAX+1][MAX+1];
int R, C;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

void mark( int r, int c ){
  int dir;
  if( r < 0 || r >= R || c < 0 || c >= C ) return;	
  if( vis[r][c] == 1 || map[r][c] == 'M') return;
  vis[r][c] = 1;
  for( dir = 0; dir < 4; dir++)
    mark( r + dx[ dir ], c + dy[ dir ]);
}

main(){
  int ncases, cases, row;
  int ri, ci, rd, cd;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%d %d", &R, &C);
    for( row = 0; row < R; row++){
      scanf("%s", map[ row ]);	
    }	
    scanf("%d %d", &ri, &ci);
    scanf("%d %d", &rd, &cd);
    memset( vis, 0, sizeof( vis ) );
    mark( ri - 1 , ci - 1 );
    if( vis[ rd - 1][ cd - 1] == 1 ) printf("SI\n");
    else printf("NO\n");
  }
  return 0;	
}

Problema D:
Problema de contar caracteres, practicamente es un for que recorra la cadena de la posicion A a la posicion B contando el caracter.

# include <string.h>
# include <stdio.h>

# define MAX_TEXT 100000

char text[MAX_TEXT + 1];

main(){
  int ncases, cases;
  int a, b, q, nquery, cont;
  char car;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%s", text);
    scanf("%d", &nquery);	
    for( q = 0; q < nquery; q++){
    	scanf(" %c %d %d", &car, &a, &b);
    	a--; b--;
    	for( cont = 0 ; a <= b ; a++ ) 
    	  if( text[ a ] == car ) cont++;
    	printf("%d\n", cont);
    }
  }
  return 0;	
}

Problema E:

El problema mas sencillo del concurso, solo hay que imprimir la tabla de multiplicar del numero dado, aqui tal vez lo que les falto en el concurso y por el motivo que fueran muchos Time Limit time limit exceeded, es por que tenian que espera esta el fin de archivo, en entrada estadar como en cualquier file, podemos leer el scanf hasta un EOF que es fin de archivo, vean el codigo para mayor comprension, tambine pueden usar la funcion foef( FIEL *pf), pero en vez de un archivo solo colocando feof( stdin ) , que indicaria entrada estandar.

# include <string.h>
# include <stdio.h>

main(){
  int dig, n;
  while( scanf("%d", &n) != EOF ){
  	for( dig = 1; dig <= 10; dig++)
  	  printf("%dx%d=%d\n", n, dig, dig * n );
  }
  return 0;	
}

Problema F:

El problema F es un problema de geometria computacional, basicamente con solo saber el algoritmo de punto en un poligono podemos resolver este problema.

# include <stdio.h>
# include <string.h>

# define MAX_POLIGON 100
# define MAX_ELEMENT 200

typedef struct { int x, y; } Point;

Point Poligon[MAX_POLIGON+1][MAX_ELEMENT+2];
int npoligon[MAX_POLIGON + 1];


int cn_PnPoly( Point P, Point* V, int n ){
    int i;
    int    cn = 0; 
    for ( i=0; i<n; i++) {    
       if (((V[i].y <= P.y) && (V[i+1].y > P.y))     /* an upward crossing */
        || ((V[i].y > P.y) && (V[i+1].y <=  P.y))) { /* a downward crossing */
            
            double vt = (double)(P.y  - V[i].y) / (double)(V[i+1].y - V[i].y);
            if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) 
                 ++cn; 
        }
    }
    return (cn&1); 

}

int hashInsidePoligon[MAX_POLIGON+1];

main(){
  int n, cont, x, y, m;
  Point source;
  while( scanf("%d", &n) != EOF && n ){
    for( x = 0; x < n; x++){
      scanf("%d", &npoligon[ x ]);	
      for( y = 0; y < npoligon[ x ] ; y++) scanf("%d %d", &Poligon[x][y].x, &Poligon[x][y].y);
      Poligon[x][y]  = Poligon[x][y-1];
    }
    memset(hashInsidePoligon, 0, sizeof(hashInsidePoligon));
    scanf("%d", &m);
    for( x = 0; x < m ; x++){
       scanf("%d %d", &source.x, &source.y );	
       for( y = 0; y < n; y++) 
         if( cn_PnPoly( source, Poligon[y] , npoligon[ y ]) )  hashInsidePoligon[ y ] = 1;
    }
    cont = 0;
    for( x = 0; x < n; x++) if(hashInsidePoligon[x] == 1) cont++;
    printf("%d\n", cont);
  }
  return 0;	
}

Cualquier duda o si quieren que explique mas a grandes rasgos una solucion me puede escribir a rodrigo.burgos@gmail.com