Cod sursa(job #167172)

Utilizator andrei.12Andrei Parvu andrei.12 Data 29 martie 2008 09:26:29
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>

#define lg 60005

int n, m, x1, x2, y1, y2, rezultat, rsp[lg], i, j;
long long a, b, c;
struct punct{
	int x, y;
};
punct v[805], pct[lg];
int main()
{
	freopen("poligon.in", "rt", stdin);
	freopen("poligon.out", "wt", stdout);
	
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i ++)
		scanf("%d%d", &v[i].x, &v[i].y);
	for (i = 1; i <= n; i ++)
		scanf("%d%d", &pct[i].x, &pct[i].y);
	
	for (i = 1; i < n; i ++){
		x1 = v[i].x, y1 = v[i].y;
		x2 = v[i+1].x, y2 = v[i+1].y;
		
		a = y1 - y2;
		b = x2 - x1;
		c = x1*y2 - x2*y1;
		
		for (j = 1; j <= m; j ++)
			if (a*pct[j].x + b*pct[j].y + c <= 0 && ((pct[j].x >= x1 && pct[j].x <= x2) || (pct[j].x <= x1 && pct[j].x >= x2)))
				rsp[j] ++;
	}
	
	for (i = 1; i <= m; i ++)
		if (rsp[i] % 2 == 1)
			rezultat ++;
	
	printf("%d\n", rezultat);
	
	return 0;
}