Cod sursa(job #307491)

Utilizator FlorianFlorian Marcu Florian Data 24 aprilie 2009 11:29:48
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<cstdio>
#include<string>
using namespace std;
#define MAX_N 666013
#define Mod 666013
#define Md 103
#define DIM 8192
char vec[DIM];
int pz;
struct Hash
{
	double x,y;
	int i;
	Hash *urm;
};
Hash *H[MAX_N];
int px[100003], py[100003]; //punctele
int ax[50003], ay[50003]; //dreptunghiurile
int N,M, W, h;
int sol;
inline void insert(double px, double py, int i)
{
	int x,y;
	x = (int)(px*10);
	y = (int)(py*10);
	int h = (x * Md + y ) % Mod;
	Hash *q = new Hash;
	q->x = px; q->y = py; q->i = i; q->urm = H[h];
	H[h] = q;
}
inline bool intersectie(int i, int x, int y)
{
	int x1 = ax[i], y1 = ay[i];
	if(x >= x1 && y>= y1 && x<= x1 + W && y <= y1 + h) return 1;
	return 0;
}	
inline bool find(double pxx, double pyx, int i)
{
	int x,y;
	bool ok = 0;
	x = (int)(pxx*10);
	y = (int)(pyx*10);
	int h = ((x * Md) + y ) % Mod;
	Hash *q;
	for(q=H[h];q;q=q->urm)
		if(q->x == pxx && q->y == pyx) { ok = 1; break; }
	if(!ok) return 0;
	if(intersectie(q->i,px[i], py[i])) return 1;
	return 0;
}
void cit(int &x)   
 {   
  x=0;   
  while(vec[pz]<'0' || vec[pz]>'9')   
  
    if(++pz==DIM) fread(vec,1,DIM,stdin),pz=0;   
  
    while(vec[pz]>='0' && vec[pz]<='9')   
    {   
        x=x*10+vec[pz]-'0';   
        if(++pz==DIM)fread(vec, 1, DIM, stdin),pz=0;   
    }   
 }   

void read()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	int i;
	cit(N); cit(M); cit(W); cit(h);
	for(i=1;i<=N;++i) { cit(ax[i]); cit(ay[i]); }
	for(i=1;i<=M;++i) { cit(px[i]); cit(py[i]); }
}
void solve()
{
	int i,j,p,k,x,y;
	for(p=1;p<=N;++p)
	{
		x= ax[p]; y=ay[p];
		i = ( (x-0.5) / W) + 1;
		j = ( (y-0.5) / h) + 1;
		insert(i*W+0.5, j*h+0.5, p);
	}
	for(p=1;p<=M;++p)
	{
		x = px[p]; y = py[p];
		i = ( (x - 0.5) / W); j = ( (y-0.5) / h);
		if(find(i*W+0.5, j*h+0.5, p) || find((i+1)*W + 0.5, j*h+0.5, p) || find(i*W+0.5, (j+1)*h+0.5, p) || find((i+1)*W+0.5, (j+1)*h+0.5,p)) ++sol;
	}
	printf("%d\n",sol);
}
int main()
{
	read();
	solve();
	return 0;
}