Cod sursa(job #1364663)

Utilizator gapdanPopescu George gapdan Data 27 februarie 2015 19:29:14
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <cstdio>
#include <vector>

#define MOD 131071
#define NMAX 50010
#define V 103
#define buffer 1<<13

using namespace std;

struct punct
{
    int x;
    int y;
};

int n, m, w, h, i, j, k, poz, sol, p1, p2;
int  l[MOD+40];
vector<int>H[MOD+30];
punct v[NMAX], p, q;

char buff[buffer]; int cnt=0;

int getInt()
{
    int number = 0;
    while(buff[cnt] < '0' || '9' < buff[cnt])
        if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0;

    while('0' <= buff[cnt] && buff[cnt] <= '9') {
        number = number * 10 + buff[cnt] - '0';
        if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0;
    }

    return number;
}

void bagahash(int x, int y)
{
    int p1, p2, sol;
    p1=x/w;
    p2=y/h;
    if(x%w==0) p1--;
    if(y%h==0) p2--;
    sol=(p1*V+p2)%MOD;
    H[sol].push_back(i);
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    n = getInt();
    m = getInt();
    w = getInt();
    h = getInt();

    for(i=1; i<=n; i++)
    {
       v[i].x = getInt();
       v[i].y = getInt();
        v[i].x++;
        v[i].y++;
        bagahash(v[i].x, v[i].y);
        bagahash(v[i].x+w, v[i].y);
        bagahash(v[i].x, v[i].y+h);
        bagahash(v[i].x+w, v[i].y+h);
    }
    for(i=1; i<=m; i++)
    {
        p.x = getInt();
        p.y = getInt();

        p.x++;
        p.y++;
        p1=(p.x)/w;
        p2=(p.y)/h;

        if((p.x)%w==0) p1--;
        if((p.y)%h==0) p2--;

        poz=(p1*V+p2)%MOD;

       for(int j = 0; j < H[poz].size(); ++j)
        {
            q=v[H[poz][j]];
            if(q.x<=p.x && p.x<=q.x+w && q.y<=p.y && p.y<=q.y+h)
            {
                sol++;
                break;
            }
        }
    }
    printf("%d\n", sol);
    return 0;
}