Cod sursa(job #316940)

Utilizator savimSerban Andrei Stan savim Data 21 mai 2009 17:56:28
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 50010

#define prim 73907
#define p1 59
#define p2 67

int n, m, w, h, i, j, sol;
struct dr {
	int x1, y1, x2, y2;
} V[MAX_N];
struct punct {
	int x, y;
} A[2 * MAX_N];
int H[prim + 10][16];

void cit() {
	freopen("ograzi.in", "r", stdin);
	freopen("ograzi.out", "w", stdout);

	scanf("%d %d %d %d", &n, &m, &w, &h);
	for (i = 1; i <= n; i++) {
		scanf("%d %d", &V[i].x1, &V[i].y1);
        V[i].x1++; V[i].y1++;

		V[i].x2 = V[i].x1 + w; 
		V[i].y2 = V[i].y1 + h;
	}
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &A[i].x, &A[i].y);
		A[i].x++; A[i].y++;
	}
}

inline int poz_x(int p) {
	if (p % w) return p / w + 1;
	else return p / w;
}

inline int poz_y(int q) {
	if (q % h) return q / h + 1;
	else return q / h;
}

void add(int p, int q, int ind) {
	p = poz_x(p);
	q = poz_y(q);

	int cell = (p * p1 + q * p2) % prim;

	H[cell][++H[cell][0]] = ind;
}

void solve() {
	//impart planul in dreptunghiuri W * H
	//vad fiecare dreptunghi din cele n date in ce celula a planului se alfa
	for (i = 1; i <= n; i++) {
		add(V[i].x1, V[i].y1, i);

		add(V[i].x1, V[i].y2, i);

		add(V[i].x2, V[i].y1, i);

		add(V[i].x2, V[i].y2, i);
	}

    //verific pentru fiecare punct daca se gaseste intr-un dreptunghi
	for (i = 1; i <= m; i++) {
		int p = poz_x(A[i].x);
		int q = poz_y(A[i].y);

		int cell = (p * p1 + q * p2) % prim;

		int ok = 0;
		for (j = 1; j <= H[cell][0]; j++) {
    		int dr = H[cell][j];

			if (V[dr].x1 <= A[i].x && A[i].x <= V[dr].x2 && V[dr].y1 <= A[i].y && A[i].y <= V[dr].y2) {
				ok = 1;
				break;
			}
		}

		if (ok) sol++;
	}

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

int main() {

    cit();
	solve();

	return 0;
}