Cod sursa(job #332260)

Utilizator freak93Adrian Budau freak93 Data 17 iulie 2009 10:42:15
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream f("ograzi.in");
ofstream g("ograzi.out");

const int prime=131071;
const int maxn=50010;
const int p1=103;
const int p2=1;

struct coord
{
    int x;
    int y;
}b[maxn*2];
struct drept
{
    int x1,y1,x2,y2;
}a[maxn];

int hash[prime+1][17];

int n,m,w,h;

int getx(int x)
{
    if(x%w)
        return x/w+1;
    else
        return x/w;
}

int gety(int y)
{
    if(y%h)
        return y/h+1;
    else
        return y/h;
}

void insert(int x,int y,int i)
{
    x=getx(x);
    y=gety(y);
    int list=x*p1+y;
    list%=prime;
    hash[list][++hash[list][0]]=i;
}

int main()
{
    f>>n>>m>>w>>h;
    for(int i=1;i<=n;++i)
    {
        f>>a[i].x1>>a[i].y1;
        ++a[i].x1;
        ++a[i].y1;
        a[i].x2=a[i].x1+w;
        a[i].y2=a[i].y1+h;
        insert(a[i].x1,a[i].y1,i);
        insert(a[i].x2,a[i].y2,i);
        insert(a[i].x1,a[i].y2,i);
        insert(a[i].x2,a[i].y1,i);
    }

    int x,y,list,j,k,points=0;

    for(int i=1;i<=m;++i)
    {
        f>>b[i].x>>b[i].y;
        ++b[i].x,++b[i].y;
        x=getx(b[i].x);
        y=gety(b[i].y);
        list=x*p1+y;
        list%=prime;

        for(j=1;j<=hash[list][0];++j)
        {
            k=hash[list][j];
            if(a[k].x1<=b[i].x&&b[i].x<=a[k].x2&&a[k].y1<=b[i].y&&b[i].y<=a[k].y2)
                break;
        }
        if(j<=hash[list][0])
            ++points;
    }
    g<<points<<"\n";

    f.close();
    g.close();

    return 0;
}