Cod sursa(job #155109)

Utilizator plastikDan George Filimon plastik Data 11 martie 2008 18:58:37
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
// Poligon, Infoarena
// http://infoarena.ro/problema/poligon

#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 1024

struct vertex {
	double x, y;
} Vert[NMAX];
vertex Edge[NMAX][2];
struct sliceEdge {
	vertex v1, v2;
	double mid;
} Slice[NMAX][NMAX];
int n, m, Len[NMAX];

bool xComp(vertex a, vertex b) {
	if (a.x == b.x)
		return (a.y < b.y ? true : false);
	return (a.x < b.x ? true : false);
}

bool yComp(sliceEdge a, sliceEdge b) {
	return (a.mid < b.mid ? true : false);
}

inline vertex segmentIntersection(vertex e[2], vertex a) {
	vertex ans;
	ans.x = ans.y = -1;
	
	if ((a.x - e[0].x) * (a.x - e[1].x) > 0)
		return ans;
	
	ans.x = a.x;
	ans.y = e[1].x * e[0].y - e[0].x * e[1].y - a.x * (e[1].y - e[0].y);
	ans.y /= (e[1].x - e[0].x);

	return ans;
}

bool above (vertex a, vertex b, int y) {
	return (y >= max(a.y, b.y));
}

int main() {

	freopen("poligon.in", "r", stdin);
	freopen("poligon.out", "w", stdout);

	scanf("%d %d", &n, &m);
	scanf("%d %d", &Vert[0].x, &Vert[0].y);
	int i;
	for (i = 1; i < n; ++ i) {
		scanf("%lf %lf", &Vert[i].x, &Vert[i].y);
		Edge[i][0] = Vert[i - 1];
		Edge[i][1] = Vert[i];
	}
	Edge[0][0] = Vert[n - 1];
	Edge[0][1] = Vert[0];

	sort(Vert, Vert + n, xComp);
	int j;
	vertex a, b;
	for (i = 0; i < n - 1; ++ i) {
		for (j = 0; j < n; ++ j) {
			//printf("Trying to add to slice %d\n", i);
		
			if (Edge[j][0].x == Edge[j][1].x)
				continue;
			a = segmentIntersection(Edge[j], Vert[i]);
			if (a.x < 0 || a.y < 0)
				continue;
			b = segmentIntersection(Edge[j], Vert[i + 1]);
			if (b.x < 0 || b.y < 0)
				continue;
			
			//printf("Segment added to slice %d\n", i);
			
			Slice[i][Len[i]].v1 = a; 
			Slice[i][Len[i]].v2 = b;
			Slice[i][Len[i]].mid = (a.y + b.y) / 2;
			++ Len[i];
		}
		
		sort(Slice[i], Slice[i] + Len[i], yComp);
		
		/*printf("Slice %d\n", i + 1);
		for (j = 0; j < Len[i]; ++ j)
			printf("(%lf %lf) (%lf %lf)\n", Slice[i][j].v1.x, Slice[i][j].v1.y, Slice[i][j].v2.x, Slice[i][j].v2.y);
		printf("\n");*/
	}
	
	double x, y;
	int step, k, ans = 0;
	
	for (i = 0; i < m; ++ i) {
		scanf("%lf %lf", &x, &y);
		
		if (x < Vert[0].x || x > Vert[n - 1].x)
			continue;
		
		for (step = 1; step < m; step <<= 1)
			;
		for (j = 0; step; step >>= 1)
			if (j + step < m && Vert[j + step].x <= x)
				j += step;
		
		if (y < min(Slice[j][0].v1.y, Slice[j][0].v2.y) || y > min(Slice[j][Len[j] - 1].v1.y, Slice[j][Len[j] - 1].v2.y))
			continue;
		
		for (step = 1; step < Len[j]; step <<= 1)
			;
		for (k = 0; step; step >>= 1)
			if (k + step < Len[j] && above(Slice[j][k + step].v1, Slice[j][k + step].v2, y))
				k += step;
		
		//printf("%d\n", k);
		
		if (k % 2 == 0)
			++ ans;
		
		//printf("(%lf %lf) in slice %d\n", x, y, j);
	}
	
	printf("%d\n", ans);
	
	return 0;
}