Cod sursa(job #1764865)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 25 septembrie 2016 23:40:09
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 50005;
const int kMod = 30013;
const int kSize = 1 << 17;
const int dx[4] = {0, -1, 0, -1};
const int dy[4] = {0, 0, -1, -1};

int n, m, w, h, cursor;
int xr[kMaxN];
int yr[kMaxN];
char buffer[kSize];
vector <int> hsh[kMod];

inline void readInt(int &v) {
    v = 0;
    while (buffer[cursor] < '0' || '9' < buffer[cursor]) {
        cursor++;
        if (cursor == kSize) {
            fread(buffer, kSize, 1, stdin);
        }
    }
    while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
        v = (v << 1) + (v << 3) + buffer[cursor] - '0';
        cursor++;
        if (cursor == kSize) {
            fread(buffer, kSize, 1, stdin);
        }
    }
}

inline int hashPair(const int x, const int y) {
    return (x * 1337 + y) % kMod;
}

int main() {
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(buffer, kSize, 1, stdin);
    readInt(n);
    readInt(m);
    readInt(w);
    readInt(h);
    for (int i = 1; i <= n; i++) {
        readInt(xr[i]);
        readInt(yr[i]);
        hsh[hashPair(xr[i] / w, yr[i] / h)].push_back(i);
    }
    
    int cnt = 0;
    while (m--) {
        int x, y;
        readInt(x);
        readInt(y);
        const int gx = x / w;
        const int gy = y / h;
        bool inside = false;
        for (int i = 0; i < 4 && !inside; i++) {
            int key = hashPair(gx + dx[i], gy + dy[i]);
            if (key > 0) {
                for (const int j: hsh[key]) {
                    if (xr[j] <= x && x <= xr[j] + w && yr[j] <= y && y <= yr[j] + h) {
                        inside = true;
                    }
                }
            }
        }
        cnt += inside;
    }
    
    printf("%d\n", cnt);
    return 0;
}