Cod sursa(job #1663262)

Utilizator tudorv96Tudor Varan tudorv96 Data 25 martie 2016 18:37:55
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

const long long MOD = 19997;

vector <pair <int, int> > M[MOD * 2];
int n, m, w, h, sol;
const int dx[] = {0, 0, -1, -1};
const int dy[] = {0, -1, 0, -1};

ifstream fin ("ograzi.in");

char P[1 << 18], *now = P;

int f(int x, int y) {
    return (1000003LL * x + y) % MOD + MOD;
}

void add(int x, int y, int key) {
    assert (key > -1 && key < MOD * 2);
    for (vector <pair <int, int> > :: iterator it = M[key].begin(); it != M[key].end(); ++it)
        if (it -> first == x && it -> second == y)
            return;
    M[key].push_back(make_pair(x, y));
}

bool query(int x, int y, int key) {
    assert (key > -1 && key < MOD * 2);
    for (vector <pair <int, int> > :: iterator it = M[key].begin(); it != M[key].end(); ++it)
        if (x >= it -> first && x <= it -> first + w && y >= it -> second && y <= it -> second + h)
            return true;
    return false;
}

void parse() {
    if (*now)
        return;
    fin.get(P, (1 << 18) - 5, '\0');
    now = P;
}

int get() {
    int x = 0;
    while (*now < '0' || *now > '9')
        ++now, parse();
    while (*now >= '0' && *now <= '9') {
        x = x * 10 + *now - '0';
        ++now, parse();
    }
    return x;
}

int main() {
    ofstream fout ("ograzi.out");

    n = get();
    m = get();
    w = get();
    h = get();
    for (int x, y, i = 0; i < n; ++i) {
        x = get();
        y = get();
        add(x, y, f(x / w, y / h));
    }
    for (int x, y, i = 0; i < m; ++i) {
        x = get();
        y = get();
        for (int k = 0; k < 4; ++k) {
            if (query(x, y, f(x / w + dx[k], y / h + dy[k]))) {
                sol++;
                break;
            }
        }
    }

    fout << sol;

    fin.close();
    fout.close();
    return 0;

}