Cod sursa(job #444235)

Utilizator katakunaCazacu Alexandru katakuna Data 19 aprilie 2010 20:03:21
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 810
#define Xmax 60010

struct latura {int x1, y1, x2, y2;} L[Nmax];
struct lat {double x1, y1, x2, y2;} aux;

int n, m, N, NB, sol, x, y, OK;
int vizX[Xmax], X[Nmax];
double x1, y1, x2, y2;
vector <lat> B[Nmax];

void citire () {
	
	int i, x1, y1, x2, y2, aux;

	scanf ("%d %d %d %d", &n, &m, &x1, &y1);
	X[ ++X[0] ] = x1; vizX[x1] = 1;
	for (i = 2; i <= n + 1; i++) {
		if (i != n + 1) scanf ("%d %d", &x2, &y2);
		else 
			x2 = L[1].x1, y2 = L[1].y1; 
		
		L[++N].x1 = x1; L[N].y1 = y1; L[N].x2 = x2; L[N].y2 = y2;
		
		if (L[N].x1 > L[N].x2 || (L[N].x1 == L[N].x2 && L[N].y1 > L[N].y2 )) {
			aux = L[N].x1, L[N].x1 = L[N].x2, L[N].x2 = aux;
			aux = L[N].y1, L[N].y1 = L[N].y2, L[N].y2 = aux;
		}
		
		if (!vizX[x2]) {
			X[ ++X[0] ] = x2;
			vizX[x2] = 1;
		}
		
		x1 = x2; y1 = y2;
	}
	
	sort (X + 1, X + X[0] + 1);
}

void intersect (int k, int l) {
	
	x1 = X[k - 1];
	double tg = (double)(L[l].y2 - L[l].y1) / (double)(L[l].x2 - L[l].x1);
	y1 = (tg * (double)(x1 - L[l].x1)) + L[l].y1;
	
	x2 = X[k];
	y2 = (tg * (double)(x2 - L[l].x1)) + L[l].y1;
}

int cmp (lat const &a, lat const &b) {
	if (a.y1 == b.y1)
		return a.y2 < b.y2;
	else
		return a.y1 < b.y1;
}

void precalc () {
	
	int i, j, a, b;
	
	for (i = 2; i <= X[0]; i++) {
		a = X[i - 1]; b = X[i];
		NB++;
		
		for (j = 1; j <= N; j++)
			if (L[j].x1 <= a && b <= L[j].x2) {
				intersect (i, j);
				aux.x1 = x1; aux.y1 = y1; aux.x2 = x2; aux.y2 = y2;
				B[NB].push_back (aux);
			}
		
		sort (B[NB].begin (), B[NB].end (), cmp);
	}
}

int egal (double a, double b) {
	
	a-= b;
	if (a < 0) a = -a;
	
	if (a < 0.00000000001) return 1;
	return 0;
}

int sub (double x1, double y1, double x2, double y2, double x3, double y3) {
	double A = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1);
	
	if ( egal (A, (double)0) ) {
		OK = 1;
		return 2;
	}
	
	if (A > 0) return 1;
	return 0;
}

int apartine (int b, int x, int y) {
	
	int p = 0, u = B[b].size () - 1, mij, ok, dr = -1;
	
	while (p <= u) {
		mij = (p + u) >> 1;
		aux = B[b][mij];
		
		ok = sub ((double)x, y, aux.x1, aux.y1, aux.x2, aux.y2);
		if (ok == 2) return 1;
		
		if ( ok ) {
			dr = mij;
			u = mij - 1;
		}
		else
			p = mij + 1;
	}
	
	if (dr != -1 && dr != 0) dr = B[b].size () - dr;
	if (dr != -1  && dr != 0 && (dr&1)) return 1;
	
	return 0;
}

void rezolva () {
	
	int p, u, mij, b, dr, k;
	for (k = 1; m; m--, k++) {
		scanf ("%d %d", &x, &y);
		OK = 0;
		
		if (x < X[1] || x > X[X[0]]) {
			continue;
		}
		
		p = 1; u = X[0];
		while (p <= u) {
			mij = (p + u) >> 1;
			if (X[mij] >= x)
				u = mij - 1;
			else 
				p = mij + 1;
		}
		
		b = u;
		if (x == X[1]) b = 1;
		
		p = 0; u = B[b].size () - 1; dr = -1;
		while (p <= u && !OK) {
			mij = (p + u) >> 1;
			aux = B[b][mij];
			
			if ( sub ((double)x, y, aux.x1, aux.y1, aux.x2, aux.y2) ) {
				dr = mij;
				u = mij - 1;
			}
			else
				p = mij + 1;
		}
		
		if (dr != -1  && dr != 0) 
			dr = B[b].size () - dr;
		if ( (dr != -1 && dr != 0 && (dr&1)) || OK || ( b + 1 <= (int) NB && x == X[b + 1] && apartine (b + 1, x, y) )) {
			sol++;
			// printf ("%d -> (%d %d)\n", k, x, y);
		}
	}
	
	printf ("%d", sol);
}

int main () {

	freopen ("poligon.in", "r", stdin);
	freopen ("poligon.out", "w", stdout);
	
	citire ();
	precalc ();
	rezolva ();
	
	return 0;
}