Cod sursa(job #344065)

Utilizator CezarMocanCezar Mocan CezarMocan Data 28 august 2009 12:57:32
Problema Poligon Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.41 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 latura {
	double x1, y1, x2, y2;
	int poz;
};

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];
double aa[maxn], bb[maxn], cc[maxn];

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

inline void build_segm(latura l, banda b, latura &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(latura a, latura b) {
	if (a.y1 + a.y2 < b.y1 + 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) / 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 parte(int poz, int x, int y) {
	double d = aa[poz] * x + bb[poz] * y + cc[poz];
	if (d < 0)
		return 1;
	if (d > 0)
		return -1;
	return 0;
}

inline int bsearch2(punct q, int left, int right) {
	int m, d1, d2;
	while (left <= right) {
		m = (left + right) / 2;
//		d1 = det(g[bd][m].x1, g[bd][m].y1, g[bd][m].x2, g[bd][m].y2, q.x, q.y);
		d1 = parte(g[bd][m].poz, q.x, q.y);
		if (d1 == 0)
			return 0;
		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);
			d2 = parte(g[bd][m + 1].poz, 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;
}

inline void build_abc(latura l) {
	double m, n;
	m = 1.0 * (l.y2 - l.y1) / (1.0 * (l.x2 - l.x1));
	n = l.y1 - m * l.x1;
	aa[i] = m; bb[i] = -1; cc[i] = n;
}


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 = 1; i <= n; i++) 
		build_abc(v[i]);
	

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

	//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);
				t.poz = j;
				g[i].push_back(t);
			}
		sort(g[i].begin(), g[i].end(), cmp);
	}


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