Cod sursa(job #326878)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 26 iunie 2009 15:19:41
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "ograzi.in"
#define file_out "ograzi.out"

#define Nmax 50100
#define Mod 110937

#define i1 81
#define i2 97

#define pb push_back

struct coord
{
	int x1,y1;
}p[Nmax],q;

int n,nr,j,xx,yy,w,h,m,aux,px,py,K;
vector<unsigned short> c[Mod];
char buffer[2*Nmax];

bool cmp(coord a, coord b)
{
	return (a.x1<b.x1);
}

void read(int &aux)
{
	aux=0;
	for(;buffer[K]<'0' || buffer[K]>'9';++K);
	for(;buffer[K]>='0' && buffer[K]<='9';++K)
		aux=aux*10+buffer[K]-'0';
}

int bs(int xx,int yy,int ls, int ld)
{
	int mij;
	
	while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if ((xx>=p[mij].x1 && xx<=p[mij].x1+w) &&
			(yy>=p[mij].y1 && yy<=p[mij].y1+h))
			return 1;
		else
		if (xx<=p[mij].x1 || yy<=p[mij].y1)
            return bs(xx,yy,ls,mij-1);
		else
		if (xx>=p[mij].x1+w || yy>=p[mij].y1+h)
            return bs(xx,yy,mij+1,ld);
	}
	
	return 0;
}

int ok(int c1, int c2)
{
	int i,ll;
	aux=(c1*i1+c2*i2)%Mod;
	for (i=0;i<c[aux].size();++i)
	{
	  if ((p[c[aux][i]].x1<=xx) && (xx<=p[c[aux][i]].x1+w) 
		&& (p[c[aux][i]].y1<=yy) && (yy<=p[c[aux][i]].y1+h)) 
		return 1;   
    }     
    return 0;   
}

int main()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	fread(buffer,1,2*Nmax,stdin);
	read(n);
	read(m);
	read(w);
	read(h);
	for (i=1;i<=n;++i)
	{
		read(p[i].x1);
		read(p[i].y1);
        q.x1=p[i].x1/w;
		q.y1=p[i].y1/h;
		aux=(q.x1*i1+q.y1*i2)%Mod;
		c[aux].pb(i);
	}
		
	//sort(p+1,p+n+1,cmp);
	
	nr=0;
	for (i=1;i<=m;++i)
	{
		read(xx);
		read(yy);
		//nr+=bs(xx,yy,1,n);
		px=xx/w;
		py=yy/h;
		if (ok(px,py) || ok(px-1,py) || ok(px,py-1) || ok(px-1,py-1))
			nr++;
	}
	
	printf("%d", nr);
	
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}