Cod sursa(job #455192)

Utilizator prisonbreakMichael Scofield prisonbreak Data 13 mai 2010 10:11:36
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.8 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 y1, y2;} aux, B[Nmax][Nmax];

int n, m, N, NB, sol, x, y, OK;
int vizX[Xmax], X[Nmax], LG[Nmax];
double x1, y1, x2, y2;

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

	scanf ("%d %d %d %d", &n, &m, &x1, &y1);
	X[ ++X[0] ] = x1; vizX[x1] = 1;
	XX = x1; YY = y1;
	
	for (i = 2; i <= n + 1; i++) {
		if (i != n + 1) scanf ("%d %d", &x2, &y2);
		else 
			x2 = XX, y2 = YY; 
		
		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;
	}
	//for (i = 1; i <= n; i++) printf ("%d %d %d %d\n", L [i].x1, L [i].y1, L [i].x2, L [i].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.y1 = y1; aux.y2 = y2;
				B[NB][ ++LG[NB] ] = aux;
			}
		
		sort (B[NB] + 1, B[NB] + LG[NB] + 1, cmp);
	}
}

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

int sub (int x1, double y1, int x2, double y2, int x3, double y3) {
	double A = double(x3 - x1) * double(y2 - y1) - double(x2 - x1) * double(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 = 1, u = LG[b], mij, ok, dr = -1;
	
	while (p <= u) {
		mij = (p + u) >> 1;
		aux = B[b][mij];
		
		ok = sub (x, (double)y, X[b], aux.y1, X[b + 1], aux.y2);
		if (ok == 2) {return 1;}
		
		if ( ok ) {
			dr = mij;
			u = mij - 1;
		}
		else
			p = mij + 1;
	}
	//printf ("dr %d\n", dr);	
	if (dr != -1) dr = LG[b] - dr + 1;
	if (dr != -1 && (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;// printf ("%d\n", b);
		//printf ("(B)->%d\n", b);
		p = 1; u = LG[b]; dr = -1;
		while (p <= u && !OK) {
			mij = (p + u) >> 1;
			aux = B[b][mij];
			
			if ( sub (x, (double)y, X[b], aux.y1, X[b + 1], aux.y2) ) {
				dr = mij;
				u = mij - 1;
			}
			else
				p = mij + 1;
		}
		//printf ("%d %d\n", dr, OK);	
		if (dr != -1) 
			dr = LG[b] - dr + 1;
		//printf ("%d\n", dr);
		if ( (dr != -1 && (dr&1)) || OK || ( b + 1 <= NB && x == X[b + 1] && apartine (b + 1, x, y) )) {
			sol++;
		//	printf ("%d -> (%d %d)\n", k, x, y);
		}
	}/*printf ("**************************************\n");
	for (int i = 1; i <= NB; i++) {
		for (int j = 1; j <= LG [i]; j++)
			printf ("%f %f\n", B [i][j].y1, B [i][j].y2);
		printf ("\n");
	}*/

	
	printf ("%d", sol);
}

int main () {

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