Cod sursa(job #324333)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 15 iunie 2009 19:26:33
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 5010

#define prim 13171
#define p1 103
#define p2 1

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 + 1][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()
{
    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);
    }

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