Pagini recente » Cod sursa (job #1135242) | Monitorul de evaluare | Cod sursa (job #1685135) | Cod sursa (job #2736362) | Cod sursa (job #1329279)
#include <fstream>
#include <algorithm>
using namespace std;
struct dr
{
int x,y;
}o[50000];
int n,m,w,h,nr,xs,xe,ox,oy;
bool cmp(dr a,dr b)
{
return a.x<b.x;
}
inline int checkx(int oaie,int st)
{
if(oaie<st)
return -1;
if(oaie<=st+w)
return 0;
return 1;
}
inline int checky(int oaie,int st)
{
if(oaie<st)
return -1;
if(oaie<=st+h)
return 0;
return 1;
}
void bsl(int s,int e)
{
if(s==e)
return;
int m=(s+e)/2,c=checkx(ox,o[m].x);
if(!c)
{
xs=m;
bsl(s,m);
}
else
bsl(m+1,e);
}
void bsr(int s,int e)
{
if(s==e)
return;
int m=(s+e)/2,c=checkx(ox,o[m].x);
if(!c)
{
xe=m;
bsr(m+1,e);
}
else
bsr(s,m);
}
void bs(int s,int e)
{
if(s==e)
return;
int m=(s+e)/2,c=checkx(ox,o[m].x);
if(!c)
{
xs=xe=m;
bsl(s,m);
bsr(m+1,e);
}
else if(c==1)
bs(m+1,e);
else
bs(s,m);
}
ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
char buffer[40], *p;
void Parse(int &x) {
x = 0;
while (*p < '0')
++p;
while (*p >= '0')
x = x * 10 + *(p++) - '0';
}
int main()
{
int i;
fin.getline(buffer, 40);
p = buffer;
Parse(n);
Parse(m);
Parse(w);
Parse(h);
for(i=0;i<n;i++) {
fin.getline(buffer, 40);
p = buffer;
Parse(o[i].x);
Parse(o[i].y);
}
sort(o,o+n,cmp);
while(m--)
{
xs=xe=-1;
fin.getline(buffer, 40);
p = buffer;
Parse(ox);
Parse(oy);
bs(0,n);
if(xs>-1)
for(i=xs;i<=xe;i++)
if(!checky(oy,o[i].y))
{
nr++;
break;
}
}
fout<<nr<<"\n";
return 0;
}