Cod sursa(job #2052439)

Utilizator zhm248Mustatea Radu zhm248 Data 30 octombrie 2017 16:44:11
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include<cstdio>
#include<vector>
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];
int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    int n,m,w,h,i,x,y,x1,y1,j,nr=0;
    scanf("%d%d%d%d",&n,&m,&w,&h);
    for(i=1; i<=n; ++i)
    {
        scanf("%d%d",&x,&y);
        x1=(2*x-1)/(2*h)+1;
        y1=(2*y-1)/(2*w)+1;
        if(!x)
            x1=0;
        if(!y)
            y1=0;
        gx[H(x1,y1)].push_back(x);
        gy[H(x1,y1)].push_back(y);
    }
    for(i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        x1=(2*x-1)/(2*h);
        y1=(2*y-1)/(2*w);
        int val=H(x1,y1);
        bool ok=0;
        if(x&&y)
        {
            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+h&&y>=vy&&y<=vy+w)
                {
                    nr++;
                    ok=1;
                    break;
                }
            }
        }
        if(!ok&&y)
        {
            x1=(2*x-1)/(2*h)+1;
            y1=(2*y-1)/(2*w);
            if(!x)
                x1=0;
            val=H(x1,y1);
            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+h&&y>=vy&&y<=vy+w)
                {
                    nr++;
                    ok=1;
                    break;
                }
            }
        }
        if(!ok&&x)
        {
            x1=(2*x-1)/(2*h);
            y1=(2*y-1)/(2*w)+1;
            if(!y)
                y1=0;
            val=H(x1,y1);
            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+h&&y>=vy&&y<=vy+w)
                {
                    nr++;
                    ok=1;
                    break;
                }
            }
        }
        if(!ok)
        {
            x1=(2*x-1)/(2*h)+1;
            y1=(2*y-1)/(2*w)+1;
            if(!x)
                x1=0;
            if(!y)
                y1=0;
            val=H(x1,y1);
            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+h&&y>=vy&&y<=vy+w)
                {
                    nr++;
                    ok=1;
                    break;
                }
            }
        }
    }
    printf("%d\n",nr);
    return 0;
}