Cod sursa(job #1199438)

Utilizator smaraldaSmaranda Dinu smaralda Data 19 iunie 2014 14:26:54
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#include<vector>
using namespace std;

const int MOD = 666013;

int height, width;

struct POINT {
    int ogx, ogy, x, y;

    POINT (int ogx = 0, int ogy = 0, int x = 0, int y = 0) {
        this->ogx = ogx;
        this->ogy = ogy;
        this->x = x;
        this->y = y;
    }
};

vector <POINT> h[MOD + 2];
//vector <POINT>::iterator it;

void get (int &i, int &j, int x, int y) {
     i = x / width;
     j = y / height;
     if(x % width) ++ i;
     if(y % height) ++ j;
}

void ins (int x, int y) {
    int i, j;

    get(i, j, x, y);

    h[(i * 47 + j * 49) % MOD].push_back(POINT(i, j, x, y));
}

bool src (int i, int j, int x1, int y1) {
    int f = (i * 47 + j * 49) % MOD;

    for(int k = 0; k < h[f].size(); ++ k) {
        int ogx = h[f][k].ogx, ogy = h[f][k].ogy, x = h[f][k].x, y = h[f][k].y;
        if(ogx == i && ogy == j && x1 >= x && x1 <= x + width && y1 >= y && y1 <= y + height)
            return 1;
    }
    return 0;
}

int main() {
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    int i, j, k, x, y, nOgr, nOi, cnt;

    scanf("%d%d%d%d", &nOgr, &nOi, &height, &width);
    for(i = 1; i <= nOgr; ++ i) {
        scanf("%d%d", &x, &y);
        ins(x, y);
    }

    cnt = 0;
    for(k = 1; k <= nOi; ++ k) {
        scanf("%d%d", &x, &y);

        get(i, j, x, y);

        if(src(i, j, x, y) || src(i - 1, j, x, y) || src(i, j - 1, x, y) || src(i - 1, j - 1, x, y))
            ++ cnt;
    }

    printf("%d", cnt);
    return 0;
}