Cod sursa(job #749178)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 15 mai 2012 23:46:39
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

struct pct
{
    int x,y,x2,y2;
};

char *buffer;
vector <pct> h[200003];

void read_int(int &x){
    while (*buffer<'0'|| *buffer>'9'){
        ++buffer;
    }

    x=0;
    while (*buffer>='0'&& *buffer<='9'){
        x=x*10+*buffer-'0';
        ++buffer;
    }
}

int main()
{
    int fs, n,m,p,q,cx,cy,r,z,i,j,a,b,sol=0;
    pct aux;
    assert(freopen("ograzi.in","r",stdin));
    fseek(stdin, 0, SEEK_END);
    fs=ftell(stdin);
    buffer=(char*)malloc(fs);
    rewind(stdin);
    assert(fread(buffer, 1, fs, stdin));
    fclose(stdin);
    
    assert(freopen("ograzi.out","w",stdout));
    
    read_int(n); read_int(m); read_int(p); read_int(q);
    for (i=1;i<=n;++i)
    {
        read_int(aux.x2); read_int(aux.y2);
        aux.x=((aux.x2+p-1)/p)*p;
        aux.y=((aux.y2+q-1)/q)*q;
        h[(aux.x*1009+aux.y)%200003].push_back(aux);
    }
    for (i=1;i<=m;++i)
    {
        read_int(a); read_int(b);
        cx=((a-1)/p)*p;
        cy=((b-1)/q)*q;
        r=(cx*1009+cy)%200003;
        z=h[r].size();
        for (j=0;j<z;++j)
            if (h[r][j].x==cx&&h[r][j].y==cy)
            {
                if (a>=h[r][j].x2&&a<=h[r][j].x2+p&&b>=h[r][j].y2&&b<=h[r][j].y2+q)
                    ++sol;
                break;
            }
        cx+=p;
        r=(cx*1009+cy)%200003;
        z=h[r].size();
        for (j=0;j<z;++j)
            if (h[r][j].x==cx&&h[r][j].y==cy)
            {
                if (a>=h[r][j].x2&&a<=h[r][j].x2+p&&b>=h[r][j].y2&&b<=h[r][j].y2+q)
                    ++sol;
                break;
            }
        cy+=q;
        r=(cx*1009+cy)%200003;
        z=h[r].size();
        for (j=0;j<z;++j)
            if (h[r][j].x==cx&&h[r][j].y==cy)
            {
                if (a>=h[r][j].x2&&a<=h[r][j].x2+p&&b>=h[r][j].y2&&b<=h[r][j].y2+q)
                    ++sol;
                break;
            }
        cx-=p;
        r=(cx*1009+cy)%200003;
        z=h[r].size();
        for (j=0;j<z;++j)
            if (h[r][j].x==cx&&h[r][j].y==cy)
            {
                if (a>=h[r][j].x2&&a<=h[r][j].x2+p&&b>=h[r][j].y2&&b<=h[r][j].y2+q)
                    ++sol;
                break;
            }
    }
    printf("%d\n",sol);
    return 0;
}