Pagini recente » Cod sursa (job #2389186) | Cod sursa (job #1098063) | Cod sursa (job #1080686) | Cod sursa (job #2807268) | Cod sursa (job #29893)
Cod sursa(job #29893)
#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;
}