Cod sursa(job #780165)

Utilizator wzrdwzrd tst wzrd Data 19 august 2012 22:56:27
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <vector>
#define DN 50005
#define MOD (1<<20)
using namespace std;

typedef vector<int>::iterator it;

int n,m,h,w,x[DN],y[DN],px,py,rez;
vector<int> hs[MOD];

int hash(int a, int b) {
    return (b<<10+a)&(0x000fffff);
}

int check(int a, int b) {
    int unde=hash(a,b);
    for(it i=hs[unde].begin(); i!=hs[unde].end(); ++i)
        if(x[*i]<=px && x[*i]+w>=px && y[*i]<=py && y[*i]+h>=py) return 1;
    return 0;
}

int main()
{
    ifstream f("ograzi.in");
    ofstream g("ograzi.out");
    f>>n>>m>>w>>h;
    for(int i=1; i<=n; ++i) {
        f>>x[i]>>y[i];
        int a=(x[i]+w)/w,b=(y[i]+h-1)/h;
        hs[hash(a,b)].push_back(i);
    }
    for(int i=1; i<=m; ++i) {
        f>>px>>py;
        int a=(px+w)/w, b=(py+h)/h;
        rez+=(check(a,b)|check(a,b-1)|check(a-1,b)|check(a-1,b-1));
    }
    g<<rez;
    return 0;
}