Cod sursa(job #1061096)

Utilizator assa98Andrei Stanciu assa98 Data 19 decembrie 2013 10:35:13
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD=66617;
const int MAX_N=50100;

int h,w;

inline int hashF(int x,int y) {
    x/=w;
    y/=h;
    return ((x%MOD)*327 + (y%MOD)*581)%MOD;
}

vector<int> H[MOD + 100];

pair<int,int> v[MAX_N];

bool intersect(int x,int y,int poz) {
    return (x>=v[poz].first && x<=v[poz].first+w) && (y>=v[poz].second && y<=v[poz].second +h);
}

const int SZ= (1<<12);
char s[SZ];
int poz;

void getNum(int &numar) {
    numar = 0;
    while (s[poz] < '0' || s[poz] > '9')
        if (++poz == SZ)
            fread(s, 1, SZ, stdin), poz = 0;
    while ('0' <= s[poz] && s[poz] <= '9') {
        numar = numar * 10 + s[poz] - '0';
        if (++poz == SZ)
            fread(s, 1, SZ, stdin), poz = 0;
    }
}
 
int main() {
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    
    int n,m;
    getNum(n);
    getNum(m);  
    getNum(w);
    getNum(h);

    for(int i=1;i<=n;i++) {
        getNum(v[i].first);
        getNum(v[i].second);

        H[ hashF( v[i].first , v[i].second) ].push_back(i);
        H[ hashF( v[i].first + w , v[i].second) ].push_back(i);
        H[ hashF( v[i].first , v[i].second + h) ].push_back(i);
        H[ hashF( v[i].first + w , v[i].second + h) ].push_back(i);
    }
    
    int ans=0;
    for(int i=1;i<=m;i++) {
        int x,y;
        getNum(x);
        getNum(y);
        for(vector<int>::iterator it=H[hashF(x,y)].begin(); it!=H[hashF(x,y)].end(); it++) {
            if(intersect(x,y,*it)) {
                ans++;
                break;
            }
        }
    }
    
    printf("%d",ans);

    return 0;
}