Pagini recente » Cod sursa (job #2108260) | Cod sursa (job #3293874) | Cod sursa (job #937785) | Cod sursa (job #636378) | Cod sursa (job #49161)
Cod sursa(job #49161)
#include<stdio.h>
#define L 200010
int x[L],y[L],np=0;
int search(int ix,int iy)
{
int li,lf,m;
li=1;
lf=np;
while(li<=lf)
{
m=(li+lf)>>1;
if(x[m]==ix && y[m]==iy)
return 1;
if(x[m]<ix || (x[m]==ix && y[m]<iy) )
li=m+1;
else
lf=m-1;
}
return 0;
}
int main()
{
FILE *fin=fopen("ograzi.in","r"),
*fout=fopen("ograzi.out","w");
int N,M,H,W,i,ix,iy,nx,ny,j,k;
fscanf(fin,"%d%d%d%d",&N,&M,&W,&H);
for(i=1;i<=N;i++)
{
fscanf(fin,"%d%d",&ix,&iy);
if(ix%W)
nx=ix-(ix%W)+W;
else
nx=ix;
if(iy%H)
ny=iy-(iy%H)+H;
else
ny=iy;
if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
{
x[++np]=nx;
y[np]=ny;
}
nx+=W;
if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
{
x[++np]=nx;
y[np]=ny;
}
ny+=H;
if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
{
x[++np]=nx;
y[np]=ny;
}
nx-=W;
if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
{
x[++np]=nx;
y[np]=ny;
}
}
//sort
for(i=1;i<=np;i++)
{
j=i;
while(j/2 && (x[j/2]<x[j] || (x[j/2]==x[j] && y[j/2]<y[j])))
{
x[j/2]^=x[j];
x[j]^=x[j/2];
x[j/2]^=x[j];
y[j/2]^=y[j];
y[j]^=y[j/2];
y[j/2]^=y[j];
j/=2;
}
}
i=np;
while(i>1)
{
x[1]^=x[i];
x[i]^=x[1];
x[1]^=x[i];
y[1]^=y[i];
y[i]^=y[1];
y[1]^=y[i];
i--;
j=1;
while(1)
{
k=j<<1;
if(k>i) break;
if(k+1<=i && (x[k+1]>x[k] || (x[k+1]==x[k] && y[k+1]>y[k])) ) k++;
if(x[j]>=x[k] || (x[j]==x[k] && y[j]>=y[k])) break;
x[j]^=x[k];
x[k]^=x[j];
x[j]^=x[k];
y[j]^=y[k];
y[k]^=y[j];
y[j]^=y[k];
j=k;
}
}
int sol=0;
for(i=1;i<=M;i++)
{
fscanf(fin,"%d%d",&ix,&iy);
if(ix%W)
nx=ix-(ix%W)+W;
else
nx=ix;
if(iy%H)
ny=iy-(iy%H)+H;
else
ny=iy;
if(search(nx,ny))
sol++;
else
{
nx+=W;
if(search(nx,ny))
sol++;
else
{
ny+=H;
if(search(nx,ny))
sol++;
else
{
nx-=W;
if(search(nx,ny))
sol++;
}
}
}
}
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;
}