Cod sursa(job #29893)

Utilizator mariusdrgdragus marius mariusdrg Data 11 martie 2007 18:41:55
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int maxn = 150001;
const int maxn1 =  50001;
const int maxn2 = 100001;

int i, j, hs;
int x[maxn1];
int x2;
int hl;
int y2;
int y[maxn1];
int ox[maxn2];
int oy[maxn2];
int n;
int m;
int nr;
int w;

vector <int> vect[maxn];

int hash(int a,int b)
{
        int h = 0;
        h ^= (h << 5) + (h >> 2) + a;
        h ^= (h << 5) + (h >> 2) + b;
        return h % maxn;

}

int main()
{
        hl = 0;
        freopen("ograzi.in","r",stdin);
        freopen("ograzi.out","w",stdout);
        hs = 0;
        scanf("%d %d %d %d",&n,&m,&w,&hs);
        for(i = 1;i <= n; ++i)
        {
                scanf("%d %d",&x[i],&y[i]);
        }
        for(j = 1;j <= m; ++j)
        {
                scanf("%d %d",&ox[j],&oy[j]);
                hl = hash(ox[j]/w,oy[j]/hs);
                vect[hash(ox[j]/w,oy[j]/hs)].push_back(j);
        }
        for(i = 1;i <= n; ++i)
        {
                vector <int>:: iterator it;
                hl = hash(x[i] / w, y[i] / hs);
                m = vect[hl].size() - 1;
                for(j = 0, it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                {
                        x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && y[i] <= oy[*it] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w + 1, y[i] / hs);
                 m = vect[hl].size() - 1;
                 for(j = 0,it = vect[hl].begin(); it != vect[hl].end() && j <= m; ++it, ++j)
                 {
                         x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && y[i] <= oy[*it] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                 --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w, y[i] / hs + 1);
                 m = vect[hl].size() - 1;
                 for(j = 0,it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                 {
                         x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && y[i] <= oy[*it] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                 --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w + 1,y[i] / hs + 1);
                 m = vect[hl].size() - 1;
                 for(j = 0, it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                 {
                         x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && y[i] <= oy[*it] + hs)
                        {
                                nr++;
                                 vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                 --j;
                                --it;
                        }
                 }
        }
        printf("%d\n",nr);
        
        return 0;
}