Cod sursa(job #1090495)

Utilizator vladrochianVlad Rochian vladrochian Data 22 ianuarie 2014 19:14:05
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#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");
int main()
{
	int i;
	fin>>n>>m>>w>>h;
	for(i=0;i<n;i++)
		fin>>o[i].x>>o[i].y;
	sort(o,o+n,cmp);
	while(m--)
	{
		xs=xe=-1;
		fin>>ox>>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;
}