Cod sursa(job #2134196)

Utilizator amaliarebAmalia Rebegea amaliareb Data 17 februarie 2018 18:34:16
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;
//ifstream f("ograzi.in");
ofstream g("ograzi.out");
const int MaxN = 50005;
const long long baza = 1e6 + 2, mod = 666013;
vector<pair<int, int> > H[mod + 1];
int n, m, w, h, ans, poz, n2;

const int BUF_SIZE = 1 << 17;
int pos = BUF_SIZE, out = 0;
char buf[BUF_SIZE], Out[BUF_SIZE], str[10];
FILE *f = fopen("ograzi.in", "r");
inline char nextch(){
    if(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, f), pos=0;
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)) ch=nextch();
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}

inline long long afla(int a, int b) {
    return ((1LL * a * baza)) + b;
}

inline bool verif(int x, int y, int b1, int b2) {
    if (b1 < 0 || b2 < 0) return 0;
    long long bucket = afla(b1, b2) % mod;
    if (H[bucket].empty()) return 0;
    for (auto drept: H[bucket])
        if(x >= drept.first && x <= drept.first + w &&
           y >= drept.second && y <= drept.second + h) return 1;
    return 0;
}

int main()
{
    n = read(); m = read(); w = read(); h = read();
    for (int i = 1; i <= n; ++i) {
        int x, y;
        x = read(); y = read();
        ++x; ++y;
        H[afla(x / (w + 1), y / (h + 1)) % mod].push_back({x, y});
    }
    for (int i = 1; i <= m; ++i) {
        int x, y;
        x = read(); y = read();
        ++x; ++y;
        int b1 = x / (w + 1), b2 = y / (h + 1);
        if (verif(x, y, b1, b2) || verif(x, y, b1 - 1, b2) || verif(x, y, b1, b2 - 1) || verif(x, y, b1 - 1, b2 - 1)) ++ans;
    }
    g << ans << '\n';
    return 0;
}