Cod sursa(job #1001170)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 24 septembrie 2013 17:43:40
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<vector>
#include<cstdlib>
#define Hval 123457
#define MOD 666013
using namespace std;
int n,m,W,H,X[50100],Y[50100],sol;
char *buffer;
vector <int> G[MOD];
int dx[]={-1,0,-1,0};
int dy[]={0,-1,-1,0};

inline void Citeste(int &x)
{
	while(*buffer<'0' || '9'<*buffer)
		buffer++;
	x=0;
	while('0'<=*buffer && *buffer<='9')
	{
		x=x*10+*buffer-'0';
		buffer++;
	}
}

inline int GetKey(int x,int y)
{
	return (1LL*x*Hval+y)%MOD;
}

inline void Add(int x,int y,int ind)
{
	int poz=GetKey(x/W,y/H);
	G[poz].push_back(ind);
}

inline void Search(int x,int y)
{
	int i,poz;
	vector <int>::iterator it;
	for(i=0;i<4;i++)
	{
		if(x/W+dx[i]<0 || y/H+dy[i]<0)
			continue;
		poz=GetKey(x/W+dx[i],y/H+dy[i]);
		for(it=G[poz].begin();it!=G[poz].end();it++)
		{
			if(X[*it]<=x && x<=X[*it]+W && Y[*it]<=y && y<=Y[*it]+H)
			{
				sol++;
				return;
			}
		}
	}
}

int main()
{
	int i,x,y;
	ifstream fin("ograzi.in");
	fin.seekg(0,ios::end);
	int fs=fin.tellg();
	fin.seekg(0,ios::beg);
	buffer=(char *)malloc(fs);
	fin.getline(buffer,fs,0);
	fin.close();
	
	Citeste(n); Citeste(m); Citeste(W); Citeste(H);
	for(i=1;i<=n;i++)
	{
		Citeste(X[i]); Citeste(Y[i]);
		Add(X[i],Y[i],i);
	}
	while(m--)
	{
		Citeste(x); Citeste(y);
		Search(x,y);
	}
	
	ofstream fout("ograzi.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}