Pagini recente » Cod sursa (job #2847795) | Cod sursa (job #1918754) | Cod sursa (job #1470037) | Cod sursa (job #1327376) | Cod sursa (job #25921)
Cod sursa(job #25921)
#include <cstdio>
#include <algorithm>
#define nmax 50005
#define mmax 100005
#define vmax 1000005
using namespace std;
int n,m,w,h;
int x[nmax],y[nmax],place[nmax];
int x1[mmax],y1[mmax],place1[mmax];
unsigned short int aib[vmax];
char s[16];
int cmp(int i,int j) {
if(x[i] < x[j]) return 1;
else if(x[i] == x[j]) return y[i] < y[j];
else return 0;
}
int cmp1(int i,int j) {
if(x1[i] < x1[j]) return 1;
else if(x1[i] == x1[j]) return y1[i] < y1[j];
else return 0;
}
int lsb(int x) {
return x ^ (x - 1) & x;
}
void update(int x,int val) {
while(x < vmax) {
aib[x] += val;
x += lsb(x);
}
}
int suma(int x) {
int r = 0;
while(x > 0) {
r += aib[x];
x -= lsb(x);
}
return r;
}
int sum(int x,int y) {
return suma(y) - suma(x - 1);
}
int main() {
freopen("ograzi.in","r",stdin);
freopen("ograzi.out","w",stdout);
scanf("%d%d%d%d\n",&n,&m,&w,&h);
for(int i = 1; i <= n; i++) {
gets(s);
int l = strlen(s),ind = 0,a = 0,b = 0;
while (s[ind] <= '9' && s[ind] >= '0') {
a = a * 10 + s[ind] - '0';
++ind;
}
while (!(s[ind] <= '9' && s[ind] >= '0')) ++ind;
while (ind < l && '0' <= s[ind] && s[ind] <= '9') {
b = b * 10 + s[ind] - '0';
++ind;
}
x[i] = a; y[i] = b;
x[i]++; y[i]++;
place[i] = i;
}
sort(place + 1,place + n + 1,cmp);
for(int i = 1; i <= m; i++) {
gets(s);
int l = strlen(s),ind = 0,a = 0,b = 0;
while (s[ind] <= '9' && s[ind] >= '0') {
a = a * 10 + s[ind] - '0';
++ind;
}
while (!(s[ind] <= '9' && s[ind] >= '0')) ++ind;
while (ind < l && '0' <= s[ind] && s[ind] <= '9') {
b = b * 10 + s[ind] - '0';
++ind;
}
x1[i] = a; y1[i] = b;
place1[i] = i;
x1[i]++; y1[i]++;
}
sort(place1 + 1,place1 + m + 1,cmp1);
int hambar_stanga = 1,hambar_dreapta = 1,cate = 0;
for(int i = 1; i <= m; i++) {
int xc = x1[place1[i]];
int yc = y1[place1[i]];
while((hambar_stanga <= min(hambar_dreapta,n)) && (x[place[hambar_stanga]] + w < xc)) {
update(y[place[hambar_stanga]], -1);
hambar_stanga++;
}
while((hambar_dreapta <= n) && (x[place[hambar_dreapta]] <= xc)) {
update(y[place[hambar_dreapta]],1);
hambar_dreapta++;
}
if(sum(yc - h,yc) >= 1) cate++;
}
printf("%d\n",cate);
return 0;
}