Cod sursa(job #344088)

Utilizator CezarMocanCezar Mocan CezarMocan Data 28 august 2009 13:56:14
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 810
#define maxX 60100
#define eps 0.000001

using namespace std;

struct punct {
	int x, y;
};

struct laturad {
	double x1, y1, x2, y2;
	int poz;
};

struct laturai {
	int x1, y1, x2, y2;
	int poz;
};


struct banda {
	int x1, x2;
};

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

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

inline void build_segm(laturai l, banda b, laturad &t) {
	double n, m;
	m = 1.0 * (l.y2 - l.y1) / (1.0 * (l.x2 - l.x1));
	n = l.y1 - m * l.x1;

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

inline bool cmp(int a, int b) {
	if (g[i][a].y1 + g[i][a].y2 < g[i][b].y1 + g[i][b].y2)
		return true;
	return false;
}

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

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

	while (left <= right) {
		m = (left + right) >> 1;
		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, poz1, poz2;
	while (left <= right) {
		m = (left + right) >> 1;
		poz1 = m; poz2 = m + 1;
//		poz1 = ind[bd][m]; poz2 = ind[bd][m + 1];
		d1 = det(g[bd][poz1].x1, g[bd][poz1].y1, g[bd][poz1].x2, g[bd][poz1].y2, q.x, q.y);
		if (d1 == 0)
			return 0;
		if (d1 == 1) {
			if (m == g[bd].size() - 1)
				return m;
			d2 = det(g[bd][poz2].x1, g[bd][poz2].y1, g[bd][poz2].x2, g[bd][poz2].y2, q.x, q.y);
			if (d2 == -1)
				return m;
			if (d2 == 0)
				return 0;
		}

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

	return 1;
}

bool cmp2(laturai a, laturai b) {
	if (a.x1 < b.x1)
		return true;
	return false;
}

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];
	}

	sort(v + 1, v + n + 1, cmp2);

	//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++) {
		nri = 0;
		for (j = 1; j <= n; j++) {
			if (v[j].x1 > b[i].x1)
				break;
			if (v[j].x1 <= b[i].x1 && b[i].x2 <= v[j].x2) {
				build_segm(v[j], b[i], t);
				t.poz = j;
				g[i].push_back(t);
				ind[nri] = nri;
				nri++;
			}
		}

		sort(ind, ind + nri, cmp);
		for (j = 0; j < nri; j++)
			sir[j] = g[i][ind[j]];
		for (j = 0; j < nri; j++)
			g[i][j] = sir[j];
	}


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

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

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

	return 0;
}