Cod sursa(job #1764852)

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

using namespace std;

const int kMaxN = 50005;

int n, m, w, h;
int xr[kMaxN];
int yr[kMaxN];
unordered_map <int64_t, int> id;

inline int64_t hashPair(const int x, const int y) {
    return ((int64_t)x << 30) + y;
}

inline bool insideRectangle(const int i, const int x, const int y) {
    return (xr[i] <= x && x <= xr[i] + h && yr[i] <= y && y <= yr[i] + w);
}

int main() {
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    
    scanf("%d %d %d %d", &n, &m, &w, &h);
    w *= 2;
    h *= 2;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &xr[i], &yr[i]);
        xr[i] *= 2;
        yr[i] *= 2;
        id[hashPair(xr[i] / h, yr[i] / w)] = i;
    }
    int cnt = 0;
    while (m--) {
        int x, y;
        scanf("%d %d", &x, &y);
        x *= 2;
        y *= 2;
        const int px = (x - 1) / h;
        const int py = (y - 1) / w;
        const int64_t hsh[] = {
            hashPair(px, py),
            hashPair(px + 1, py),
            hashPair(px, py + 1),
            hashPair(px + 1, py + 1)
        };
        bool inside = false;
        for (int i = 0; i < 4 && !inside; i++) {
            unordered_map <int64_t, int> :: iterator it = id.find(hsh[i]);
            if (it != id.end()) {
                inside |= insideRectangle(it->second, x, y);
            }
        }
        cnt += inside;
    }
    
    printf("%d\n", cnt);
    return 0;
}