Cod sursa(job #1329279)

Utilizator vladrochianVlad Rochian vladrochian Data 29 ianuarie 2015 12:33:01
Problema Ograzi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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");
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;
}