Cod sursa(job #521904)

Utilizator cosmyoPaunel Cosmin cosmyo Data 13 ianuarie 2011 19:10:13
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <vector>
#define x first 
#define y second 
using namespace std;
const int N = 805;
int n, m, X, Y;
pair<int, int> p[N];

int sgn(int x1, int y1, int x2, int y2, int x3, int y3) {
	long long a =(long long) x1 * y2 +(long long) x2 * y3 +(long long) x3 * y1 - ((long long)x3 * y2 +(long long) x1 * y3 +(long long) x2 * y1);
	if(a < 0)
		return -1;
	if(a ==0)
		return 0;
	if(a > 0)
		return  1;
}
int intersection(int x1, int y1, int X1, int Y1, int x2, int y2, int X2, int Y2) {
	if(sgn(x1, y1, X1, Y1, x2, y2) != sgn(x1, y1, X1, Y1, X2, Y2))
		if(sgn(x2, y2, X2, Y2, x1, y1) != sgn(x2, y2, X2, Y2, X1, Y1))
			return 1;
	return 0;
}
int main() {
	freopen("poligon.in", "r", stdin);
	freopen("poligon.out", "w", stdout);
	int i, j, nr, K = 0;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= n; ++i)
		scanf("%d %d", &p[i].x, &p[i].y);
	p[n + 1] = p[1];
	for(i = 1; i <= m; ++i) {
		scanf("%d %d", &X, &Y);
		nr = 0;
		for(j = 1; j <= n; ++j)
			if(intersection(p[j].x, p[j].y, p[j + 1].x, p[j + 1].y, X, Y, X, 60005))
				++nr;
		if(nr % 2 == 1)
			++K;
	}
	
	printf("%d \n", K);

	return 0;
}