Pagini recente » Cod sursa (job #2436094) | Cod sursa (job #2003473) | Cod sursa (job #2277838) | Cod sursa (job #1174956) | Cod sursa (job #29921)
Cod sursa(job #29921)
#include <stdio.h>
#include<string.h>
#include <vector>
using namespace std;
const int maxn = 254312;
const int maxn1 = 50001;
const int maxn2 = 100001;
int i, j, hs;
int x[maxn1];
int x2;
int hl;
int y2;
char s1[maxn1];
int pr;
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 >> 3) + a;
h ^= (h << 5) + (h >> 3) + 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)
{
fgets(s1,100,stdin);
j = 0;
pr = 0;
while(s1[j] != ' ')
{
pr *= 10;
pr += s1[j] - '0';
++j;
}
++j;
x[i] = pr;
pr = 0;
while(s1[j] != '\n')
{
pr *= 10;
pr += s1[j] - '0';
++j;
}
y[i] = pr;
}
for(i = 1;i <= m; ++i)
{
fgets(s1,100,stdin);
j = 0;
pr = 0;
while(s1[j] != ' ')
{
pr *= 10;
pr += s1[j] - '0';
++j;
}
++j;
ox[i] = pr;
pr = 0;
while(s1[j] != '\n')
{
pr *= 10;
pr += s1[j] - '0';
++j;
}
oy[i] = pr;
hl = hash(ox[i]/w,oy[i]/hs);
vect[hash(ox[i]/w,oy[i]/hs)].push_back(i);
}
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] && oy[*it] <= y[i] + 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] && oy[*it] <= y[i] + 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] && oy[*it] <= y[i] + 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] && oy[*it] <= y[i] + hs)
{
nr++;
vect[hl][j] = vect[hl][m];
vect[hl].pop_back();
m--;
--j;
--it;
}
}
}
printf("%d\n",nr);
return 0;
}