Cod sursa(job #80558)

Utilizator cosminpdrfischer2004 cosminp Data 28 august 2007 16:38:15
Problema Poligon Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>

#define INF 100000

struct punct {
	int x, y; 
}; 
typedef struct punct punct; 

punct P[1000], T, TLim; 
int N, M; 

long cross(punct A, punct B, punct C)
{
	int prod; 
	
	prod =  (A.x - B.x)*(A.y - C.y) - (A.y - B.y)*(A.x - C.x); 
	
	if (prod < 0)
		return -1;
	if (prod > 0)
		return 1;
	return prod; 
}	

long intersect(punct A, punct B, punct C, punct D) // AB se intersecteaza cu CD
{
	long d1, d2, d3, d4;
	
	
	d1 = cross(A, B, C);
	d2 = cross(A, B, D);
	d3 = cross(C, D, A); 
	d4 = cross(C, D, B); 
	return ((d1 * d2 <= 0) && (d3 * d4 <= 0));
}	 

int interiorP(punct T)
{
	int i, NrLaturi = 0;
	
	
	TLim.y = T.y + 997;
	
	
	for (i = 0; i < N; i++)
	{
		if (T.x == P[i].x && T.y == P[i].y)
			return 1;
		if (intersect(P[i], P[i+1], T, TLim))
			NrLaturi++; 
	}
	
	return NrLaturi%2;
}

int main()
{
	int i, NrSol = 0; 
	
	freopen("poligon.in", "rt", stdin);
	freopen("poligon.out", "wt", stdout); 
	
	TLim.x = 0; 
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
		scanf("%d %d", &P[i].x, &P[i].y);
		
	P[N].x = P[0].x, P[N].y = P[0].y;
	
	TLim.x = INF; 
	while (M--)
	{
		scanf("%d %d", &T.x, &T.y);
		if (interiorP(T))
			NrSol++;
	}
	fclose(stdin); 
	
	printf("%d", NrSol); 
	fclose(stdout); 
	return 0; 
}