Cod sursa(job #1561987)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 4 ianuarie 2016 18:34:00
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int md=666013;
//whatcha gunna do
int w,h;
struct sp
{
    int x,y;
};
vector<sp> a[md+3];
int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    int n,m,i,j,x,y,xi,yi,xj,yj,nr=0;
    sp tm;
    scanf("%d%d%d%d",&n,&m,&w,&h);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&y);
        tm.x=x;
        tm.y=y;
        xi=(x/w);
        yi=(y/h);
        xj=(xi+1);
        yj=(yi+1);
        a[(xi*1007+yi)%md].push_back(tm);
        a[(xi*1007+yj)%md].push_back(tm);
        a[(xj*1007+yi)%md].push_back(tm);
        a[(xj*1007+yj)%md].push_back(tm);
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        xi=x/w;
        yi=y/h;
        xi=(xi*1007+yi)%md;
        for(j=a[xi].size()-1; j>=0; j--)
        {
            tm=a[xi][j];
            if(tm.x<=x && x<=tm.x+w && tm.y<=y && y<=tm.y+h)
                break;
        }
        if(j>=0)
            nr++;
    }
    printf("%d\n",nr);
    return 0;
}