Cod sursa(job #307419)

Utilizator FlorianFlorian Marcu Florian Data 24 aprilie 2009 09:41:33
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>
using namespace std;
#define MAX_N 666013
#define Mod 666013
#define Md 103
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 read()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	int i;
	scanf("%d%d%d%d",&N,&M,&W,&h);
	for(i=1;i<=N;++i) scanf("%d%d",&ax[i],&ay[i]);
	for(i=1;i<=M;++i) scanf("%d%d",&px[i],&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;
}