Pagini recente » Cod sursa (job #2663068) | Cod sursa (job #1452269) | Cod sursa (job #1157027) | Cod sursa (job #2107077) | Cod sursa (job #1419548)
#include<algorithm>
#include<cstdio>
#define N 50000
using namespace std;
struct punct{
int x,y;
};
struct dreptunghi{
int v[4];
int x,y;
};
punct ogr[N+1];
dreptunghi d[N*4+1];
int w,h,n;
char s[20];
punct get(){
int j=0;
punct p;
gets(s);
p.x=0;
while(s[j]!=' '){
p.x=p.x*10+s[j]-'0';
j++;
}
j++;
p.y=0;
while(s[j]!=NULL){
p.y=p.y*10+s[j]-'0';
j++;
}
return p;
}
bool meow(dreptunghi a,dreptunghi b){
if (a.x<b.x) return true;
if (a.x==b.x &&a.y<b.y) return true;
return false;
}
void add(int i,int j){
if (d[j].v[0]!=0) d[i].v[0]=d[j].v[0];
else
if (d[j].v[1]!=0) d[i].v[1]=d[j].v[1];
else
if (d[j].v[2]!=0) d[i].v[2]=d[j].v[2];
else d[i].v[3]=d[j].v[3];
}
int cb(punct pct){
int poz,pas;
pas=(1<<17);
poz=0;
pct.x=pct.x/w+1;
pct.y=pct.y/h+1;
while(pas>0){
if (poz+pas<n &&d[poz+pas].x<pct.x) poz+=pas;
pas>>=1;
}
pas=(1<<17);
while(pas>0){
if (poz+pas<n &&d[poz+pas].x==pct.x &&d[poz+pas].y<pct.y) poz+=pas;
pas>>=1;
}
return poz;
}
bool ap(punct p,int i){
if (d[i].v[0]!=0){
if (p.x<=ogr[d[i].v[0]].x+w &&p.y<=ogr[d[i].v[0]].y+h) return true;
}
else
if (d[i].v[1]!=0){
if (p.x<=ogr[d[i].v[1]].x+w &&p.y>=ogr[d[i].v[1]].y) return true;
}
else
if (d[i].v[2]!=0){
if (p.x>=ogr[d[i].v[2]].x &&p.y>=ogr[d[i].v[2]].y) return true;
}
else
if (d[i].v[3]!=0){
if (p.x>=ogr[d[i].v[3]].x &&p.y<=ogr[d[i].v[3]].y+h) return true;
}
return false;
}
int main(){
freopen ("ograzi.in","r",stdin);
freopen ("ograzi.out","w",stdout);
int m,i,j,aux,cnt;
punct p;
scanf ("%d%d%d%d\n",&n,&m,&w,&h);
j=0;
for(i=1;i<=n;i++){
//scanf ("%d%d",&ogr[i].x,&ogr[i].y);
ogr[i]=get();
j++;
d[j].v[2]=i;
d[j].x=ogr[i].x/w+1;
d[j].y=ogr[i].y/h+1;
j++;
d[j].v[1]=i;
d[j].x=ogr[i].x/w+2;
d[j].y=ogr[i].y/h+1;
j++;
d[j].v[3]=i;
d[j].x=ogr[i].x/w+1;
d[j].y=ogr[i].y/h+2;
j++;
d[j].v[0]=i;
d[j].x=ogr[i].x/w+2;
d[j].y=ogr[i].y/h+2;
}
sort(d+1,d+n*4+1,meow);
j=1;
for(i=2;i<=n*4;i++){
if (d[i].x==d[j].x &&d[i].y==d[j].y) add(j,i);
else {
j++;
d[j]=d[i];
}
}
n=j;
cnt=0;
for(i=1;i<=m;i++){
//scanf ("%d%d",&p.x,&p.y);
p=get();
aux=cb(p)+1;
if (d[aux].x==p.x/w+1 &&d[aux].y==p.y/h+1)
if (ap(p,aux)) cnt++;
}
printf ("%d",cnt);
return 0;
}