Pagini recente » Cod sursa (job #2711232) | Cod sursa (job #1235491) | Cod sursa (job #2979455) | Cod sursa (job #2174499) | Cod sursa (job #26702)
Cod sursa(job #26702)
#include <stdio.h>
#include <string.h>
long n,m,w,h;
long nroi;
struct coord{long x;long y;} ogr[50002],aux;
long poz(long p,long u)
{ long x,st,dr; x=ogr[p].x; st=p; dr=u;
while(st<dr)
{ while(st<dr && x<=ogr[dr].x) dr--; ogr[dr]=ogr[st];
while(st<dr && x>=ogr[st].y) st++; ogr[st]=ogr[dr];
} ogr[st].x=x; return st;
}
void Quick_sort(long p,long u)
{ long m;
if(p<u) { m=poz(p,u);
Quick_sort(p,m-1);
Quick_sort(m+1,u);
}
}
void bubbles(){
int b,i;
do{b=0;
for(i=1;i<n;i++)
if(ogr[i].x==ogr[i+1].x)
if(ogr[i].y>ogr[i+1].y)
{aux=ogr[i];
ogr[i]=ogr[i+1];
ogr[i]=aux;
b=1;}
}while(b);
}
//INTERSCHIMBARE();
/*void interschimbare(){
long i,j;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(ogr[i][0]>ogr[j][0]){aux=ogr[i][0];
ogr[i][0]=ogr[j][0];
ogr[j][0]=aux;
aux=ogr[i][1];
ogr[i][1]=ogr[j][1];
ogr[j][1]=aux;
}
if(ogr[i][0]==ogr[j][0]&&ogr[i][1]>ogr[j][1]){aux=ogr[i][0];
ogr[i][0]=ogr[j][0];
ogr[j][0]=aux;
aux=ogr[i][1];
ogr[i][1]=ogr[j][1];
ogr[j][1]=aux; }
}
}
}*/
int cautare(long x,long y){
long st,dr,c;
st=1;
dr=n;
while(dr>=st){
c=(dr+st)/2;
if(x>=ogr[dr].x&&x<=ogr[dr].x+w)
if(y>=ogr[dr].y&&y<=ogr[dr].y+h){ return 1;}
if(x>=ogr[st].x&&x<=ogr[st].x+w)
if(y>=ogr[st].y&&y<=ogr[st].y+h){ return 1;}
if(x<ogr[c].x){ dr=c-1;continue;}
if(x>ogr[c].x+w){ st=c+1;continue;}
if(x>=ogr[c].x&&x<=ogr[c].x+w){
if(y<ogr[c].y){ dr=c-1;continue;}
if(y>ogr[c].y+h){ st=c+1;continue;}
if(y>=ogr[c].y&&y<=ogr[c].y+h){ return 1;}
if(dr==st) return 0;
}
}
return 0;
}
void citire(){
FILE *in;
long i,x,y;
char aux[1000];
in=fopen("ograzi.in","r");
// fgets(aux,1000,in);
fscanf(in,"%ld %ld %ld %ld",&n,&m,&w,&h);
for(i=1;i<=n;i++){
fgets(aux,1000,in);
fscanf(in,"%ld %ld",&ogr[i].x,&ogr[i].y);
}
Quick_sort(1,n);
bubbles();
//interschimbare();
for(i=1;i<=m;i++){
fscanf(in,"%ld %ld",&x,&y);
nroi=nroi+cautare(x,y);
// procesare(x,y);
}
}
void scriere(){
FILE *out;
out=fopen("ograzi.out","w");
fprintf(out,"%ld",nroi);
}
int main(){
citire();
scriere();
return 0;
}