Pagini recente » Cod sursa (job #961004) | Cod sursa (job #879792) | Cod sursa (job #1778893) | Cod sursa (job #2181483) | Cod sursa (job #26595)
Cod sursa(job #26595)
#include <stdio.h>
long n,m,w,h;
long nroi;
long ogr[51002][3],aux;
void procesare(long x,long y){
long i;
for(i=0;i<n;i++){
if(x>=ogr[i][0]&&x<=ogr[i][0]+w&&y>=ogr[i][1]&&y<=ogr[i][1]+h) {nroi++;break;}
}
}
/*void qsort(long l,long r)
{long i,j,mij;
i=l;j=r;
mij=ogr[(i+j)/2].x;
do{ while(ogr[i].x<mij) i++;
while(ogr[j].y>mij) j--;
if(i<=j) {if(i<j) {aux=ogr[i];
ogr[i]=ogr[j];
ogr[j]=aux; }
i++; j--;}
}while(i<=j);
if(l>j) qsort(l,j);
if(i<r) qsort(i,r);
}
*/
//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[c][0]){ dr=c-1;continue;}
if(x>ogr[c][0]+w){ st=c+1;continue;}
if(x>=ogr[c][0]&&x<=ogr[c][0]+w){
if(y<ogr[c][1]){ dr=c-1;continue;}
if(y>ogr[c][1]+h){ st=c+1;continue;}
if(y>=ogr[c][1]&&y<=ogr[c][1]+h){ return 1;}
}
}
return 0;
}
void citire(){
FILE *in;
long i,x,y;
in=fopen("ograzi.in","r");
fscanf(in,"%ld %ld %ld %ld",&n,&m,&w,&h);
for(i=1;i<=n;i++){
fscanf(in,"%ld %ld",&ogr[i][0],&ogr[i][1]);
}
// qsort(0,n);
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;
}