Cod sursa(job #344034)

Utilizator CezarMocanCezar Mocan CezarMocan Data 28 august 2009 11:58:21
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.3 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 810
#define maxX 60100

using namespace std;

struct punct {
	int x, y;
};

struct latura {
	int x1, y1, x2, y2;
};

struct banda {
	int x1, x2;
};

int n, m, i, j, nrb, x, y, bd, sol, nr;
punct p[maxn], q;
bool fol[maxX];
latura v[maxn], t;
banda b[maxn];
int aux[maxn];
vector <latura> g[maxn];

inline void swap(int &a, int &b) {
	int aux;
	aux = a; a = b; b = aux;
}

void build_segm(latura l, banda b, latura &t) {
	int n, m;
	m = (l.y2 - l.y1) / (l.x2 - l.x1);
	n = l.y1 - m * l.x1;

//	fprintf(stderr, "%d %d  %d %d    %d %d    %d %d\n", l.x1, l.y1, l.x2, l.y2, m, n, b.x1, b.x2);

	t.x1 = b.x1; t.y1 = m * t.x1 + n;
	t.x2 = b.x2; t.y2 = m * t.x2 + n;

//	fprintf(stderr, "%d %d  %d %d\n\n", t.x1, t.y1, t.x2, t.y2);
}

inline bool cmp(latura a, latura b) {
	if (a.x1 + a.x2 < b.x1 + b.x2)
		return true;
	return false;
}

inline int det(int x1, int y1, int x2, int y2, int x3, int y3) {
	int d = (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3);
	if (d > 0)
		return 1;
	if (d < 0)
		return -1;
	return 0;
}

inline int bsearch1(int val, int left, int right) {
	int m;

	while (left <= right) {
		m = (left + right) / 2;
		if (b[m].x1 < val && val <= b[m].x2)
			return m;
		if (val <= b[m].x1)
			right = m - 1;
		else
			left = m + 1;
	}

	return -1;
}

inline int bsearch2(punct q, int left, int right) {
	int m, d1, d2;
	while (left <= right) {
		m = (left + right) / 2;
//		fprintf(stderr, "%d\n", m);
		d1 = det(g[bd][m].x1, g[bd][m].y1, g[bd][m].x2, g[bd][m].y2, q.x, q.y);
		if (d1 == 1) {
			if (m == g[bd].size() - 1)
				return m;
			d2 = det(g[bd][m + 1].x1, g[bd][m + 1].y1, g[bd][m + 1].x2, g[bd][m + 1].y2, q.x, q.y);
			if (d2 == -1)
				return m;
			if (d2 == 0)
				return 1;
		}

		if (d1 == 1)
			left = m + 1;
		else
			right = m - 1;
	}	

	return 0;
}

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

	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &p[i].x, &p[i].y);
		fol[p[i].x] = 1;
	}

	p[n + 1] = p[1];
	for (i = 1; i <= n; i++) {
		v[i].x1 = p[i].x; v[i].y1 = p[i].y;
		v[i].x2 = p[i + 1].x; v[i].y2 = p[i + 1].y;

		if (v[i].x1 > v[i].x2) {
			swap(v[i].x1, v[i].x2);
			swap(v[i].y1, v[i].y2);
		}
	}

	for (i = 0; i <= 60000; i++)
		if (fol[i]) {
			nrb++;
			aux[nrb] = i;
		}

	nrb--;
	for (i = 1; i <= nrb; i++) {
		b[i].x1 = aux[i];
		b[i].x2 = aux[i + 1];
//		fprintf(stderr, "%d %d\n", b[i].x1, b[i].x2);
	}

	//pana aici am laturile si am regiunile
	//urmeaza sa fac un N^2 ca sa vad pentru fiecare regiune ce laturi sunt in ea

	for (i = 1; i <= nrb; i++) {
		for (j = 1; j <= n; j++)
			if (v[j].x1 <= b[i].x1 && b[i].x2 <= v[j].x2) {
				build_segm(v[j], b[i], t);
				g[i].push_back(t);
			}
		sort(g[i].begin(), g[i].end(), cmp);
	}

/*	for (i = 1; i <= nrb; i++) {
		for (j = 0; j < g[i].size(); j++)
			fprintf(stderr, "%d %d  %d %d\n", g[i][j].x1, g[i][j].y1, g[i][j].x2, g[i][j].y2);
		fprintf(stderr, "\n");
	}*/

	for (i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		q.x = x; q.y = y;

		bd = bsearch1(x, 1, nrb);
//		fprintf(stderr, "%d %d\n", i, bd);
		if (bd != -1) {
			nr = bsearch2(q, 0, g[bd].size() - 1); // sa nu uit sa returnez 1 daca punctu e pe vreuna din drepte
//			fprintf(stderr, "%d\n\n", nr);
			sol += (1 - nr % 2);
		}
	}

	printf("%d\n", sol);

	return 0;
}