Cod sursa(job #1562011)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 4 ianuarie 2016 18:52:51
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int size=10000000;
const int md=666013;
//whatcha gunna do
char si[size];
int w,h,cit;
struct sp
{
    int x,y;
};
vector<sp> a[md+3];
int get()
{
    int ans=0;
    while(si[cit]>='0' && si[cit]<='9')
    {
        ans=ans*10+si[cit]-'0';
        cit++;
    }
    cit++;
    return ans;
}
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;
    fread(si,sizeof(char),size,stdin);
    cit=0;
    n=get();
    m=get();
    w=get();
    h=get();
    for(i=1; i<=n; i++)
    {
        x=get();
        y=get();
        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++)
    {
        x=get();
        y=get();
        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;
}