Cod sursa(job #2273725)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 31 octombrie 2018 21:11:27
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<cstdio>

#include<vector>

#include<cstring>

#include<cctype>

using namespace std;

const int p1=1009;

const int p2=37193;

int H(int x,int y)

{

    return (x*p1+y)%p2;

}

vector<int>gx[p2+1];

vector<int>gy[p2+1];

char s[20];

int main()

{

    freopen("ograzi.in","r",stdin);

    freopen("ograzi.out","w",stdout);

    int n,m,w,h,i,x,y,j,nr=0,k;

    scanf("%d%d%d%d\n",&n,&m,&w,&h);

    for(i=1; i<=n; ++i)

    {

        gets(s);

        k=strlen(s);

        x=0;

        y=0;

        for(j=0;isdigit(s[j]);++j)

        {

            x=(10*x)+(s[j]-'0');

        }

        ++j;

        for(;j<k;++j)

        {

            y=(10*y)+(s[j]-'0');

        }

        gx[H(x/w,y/h)].push_back(x);

        gy[H(x/w,y/h)].push_back(y);

    }

    for(i=1; i<=m; ++i)

    {

        gets(s);

        k=strlen(s);

        x=0;

        y=0;

        for(j=0;isdigit(s[j]);++j)

        {

            x=(10*x)+(s[j]-'0');

        }

        ++j;

        for(;j<k;++j)

        {

            y=(10*y)+(s[j]-'0');

        }

        int val;

        bool ok=0;

        val=H(x/w,y/h);

        for(j=0; j<gx[val].size()&&j<gy[val].size(); ++j)

        {

            int vx=gx[val][j];

            int vy=gy[val][j];

            if(x>=vx&&x<=vx+w&&y>=vy&&y<=vy+h)

            {

                nr++;

                ok=1;

                break;

            }

        }

        if(!ok&&(y/h))

        {

            val=H(x/w,y/h-1);

            for(j=0; j<gx[val].size()&&j<gy[val].size(); ++j)

            {

                int vx=gx[val][j];

                int vy=gy[val][j];

                if(x>=vx&&x<=vx+w&&y>=vy&&y<=vy+h)

                {

                    nr++;

                    ok=1;

                    break;

                }

            }

        }

        if(!ok&&(x/w))

        {

            val=H(x/w-1,y/h);

            for(j=0; j<gx[val].size()&&j<gy[val].size(); ++j)

            {

                int vx=gx[val][j];

                int vy=gy[val][j];

                if(x>=vx&&x<=vx+w&&y>=vy&&y<=vy+h)

                {

                    nr++;

                    ok=1;

                    break;

                }

            }

        }

        if(!ok&&(x/w)&&(y/h))

        {

            val=H(x/w-1,y/h-1);

            for(j=0; j<gx[val].size()&&j<gy[val].size(); ++j)

            {

                int vx=gx[val][j];

                int vy=gy[val][j];

                if(x>=vx&&x<=vx+w&&y>=vy&&y<=vy+h)

                {

                    nr++;

                    ok=1;

                    break;

                }

            }

        }

    }

    printf("%d\n",nr);

    return 0;

}