Cod sursa(job #2134135)

Utilizator amaliarebAmalia Rebegea amaliareb Data 17 februarie 2018 17:48:43
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;
//ifstream f("ograzi.in");
ofstream g("ograzi.out");
const int MaxN = 50005, MaxM = 100005;
map<pair<int, int>, int> H;
int n, m, w, h, ans, poz, n2;
pair<int, int> v[MaxN];
vector<pair<int, int> > hh[MaxN];

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 bool verif(int x, int y) {
    return x >= v[poz].first && x <= v[poz].first + w &&
           y >= v[poz].second && y <= v[poz].second + h;
}

inline void cauta(vector<pair<int, int> > hh) {
    int sz = hh.size();
    for (int i = 0; i < sz; ++i) {
        if (verif(hh[i].first, hh[i].second)) {
            ++ans;
            swap(hh[i], hh[sz - 1]);
            hh.pop_back();
            --sz;
            --i;
        }
    }
}

int main()
{
    n = read(); m = read(); w = read(); h = read();
    for (int i = 1; i <= n; ++i) {
        int x, y;
        x = read(); y = read();
        v[i] = {x, y};
    }
    for (int i = 1; i <= m; ++i) {
        int x, y;
        x = read(); y = read();
        pair<int, int> bucket = {x / w, y / h};
        if (H[bucket]) hh[H[bucket]].push_back({x, y});
        else {
            H[bucket] = ++ n2;
            hh[n2].push_back({x, y});
        }
    }
    for (int i = 1; i <= n; ++i) {
        int x = v[i].first, y = v[i].second, b1 = x / w, b2 = y / h;
        poz = i;
        cauta(hh[H[{b1, b2}]]);
        cauta(hh[H[{b1 + 1, b2}]]);
        cauta(hh[H[{b1, b2 + 1}]]);
        cauta(hh[H[{b1 + 1, b2 + 1}]]);
    }
    g << ans << '\n';
    return 0;
}