Cod sursa(job #755595)

Utilizator GrimpowRadu Andrei Grimpow Data 6 iunie 2012 15:01:37
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <vector>

using namespace std;

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

vector <pct> h[200003];

int main()
{
    int n,m,p,q,cx,cy,r,z,i,j,a,b,sol=0;
    pct aux;
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    scanf("%d %d %d %d\n",&n,&m,&p,&q);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d\n",&aux.x2,&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)
    {
        scanf("%d %d\n",&a,&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;
}