Pagini recente » Cod sursa (job #165001) | Cod sursa (job #459618) | Cod sursa (job #1596484) | Cod sursa (job #763543) | Cod sursa (job #25844)
Cod sursa(job #25844)
#include <stdio.h>
#include <fstream>
#include <math.h>
using namespace std;
#define in "ograzi.in"
#define out "ograzi.out"
#define dim 50001
struct punct {
int x1, y1, x2, y2;
} p[dim], oi[dim];
int n, m, w, h;
void Qsorty(int,int);
int BinaryS(int,int);
int main()
{
freopen(in,"r",stdin);
FILE *fin = fopen("ograzi.in","r");
freopen(out,"w",stdout);
char line[21];
int j = 0;
int number=0;
fscanf(fin,"%d%d%d%d",&n,&m,&w,&h);
fscanf(fin,"\n");
for ( int i = 1; i <= n; i++ )
{
fgets(line,20,fin);
j=0;
number=0;
while(line[j]>='0' && line[j]<='9')
{
number=number*10+(line[j]-'0');
j++;
}
p[i].x1=number;
j++;
number=0;
while(line[j]>='0' && line[j]<='9')
{
number=number*10+(line[j]-'0');
j++;
}
p[i].y1=number;
p[i].x2 = p[i].x1 + w;
p[i].y2 = p[i].y1 + h;
}
Qsorty(1,n);
/* int k = sizeof(p);
printf("%d\n",k);*/
for ( int i = 1; i <= m; i++ )
{
fgets(line,20,fin);
j=0;
number=0;
while(line[j]>='0' && line[j]<='9')
{
number=number*10+(line[j]-'0');
j++;
}
oi[i].x1=number;
j++;
number=0;
while(line[j]>='0' && line[j]<='9')
{
number=number*10+(line[j]-'0');
j++;
}
oi[i].y1=number;
}
int t=0;
for ( int i = 1; i <= m; i++ )
{
if ( BinaryS(oi[i].x1,oi[i].y1) == 1 )
{
t+=1;
}
}
printf("%d", t);
}
void Qsorty(int st, int dr)
{
int i = st-1;
int j = dr+1;
int pivotx = p[st].x1;
int pivoty = p[st].y1;
while ( i <= j )
{
do { i++; } while ( pivoty > p[i].y1 || pivoty==p[i].y1 && pivotx > p[i].x1 );
do { j--; } while ( p[j].y1 > pivoty || pivoty==p[j].y1 && p[j].x1 > pivotx );
if ( i <= j )
{
punct aux = p[i];
p[i] = p[j];
p[j] = aux;
}
}
if ( st < j ) Qsorty(st,j);
if ( i < dr ) Qsorty(i,dr);
}
int BinaryS(int a,int b)
{
int st = 1;
int dr = n;
int ok = 0;
// printf("V : ");
while ( st <= dr )
{
int mij = (st+dr)/2;
if ( p[mij].y1 > b )
{
dr = mij-1;
}
else
{
if ( p[mij].y2 < b )
{
st = mij + 1;
}
else
{
if ( p[mij].y1 <= b && p[mij].y2 >= b )
{
// printf("%d ", mij);
int k = mij;
while ( p[k].y1 <= b && p[k].y2 >= b && ok == 0 )
{
if ( p[k].x1 <= a && p[k].x2 >= a )
{
ok = 1;
st = dr+1;
}
k++;
}
if ( !ok )
{
while ( p[mij].y1 <= b && p[mij].y2 >= b && ok == 0 )
{
if ( p[mij].x1 <= a && p[mij].x2 >= a )
{
ok = 1;
st = dr+1;
}
mij--;
}
}
if ( !ok ) st = dr+1;
}
}
}
}
//printf("\n");
return ok;
}