Cod sursa(job #555134)

Utilizator ooctavTuchila Octavian ooctav Data 15 martie 2011 12:03:31
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"ograzi.in"};
const char OUT[] = {"ograzi.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 50005;
const int MMAX = 100005;
const int CIFMAX = 17;
const int COORDMAX = 10000;
const int MOD1 = 104723;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N, M, W, H;
PII c[NMAX], o[MMAX];
vector<int> h1[MOD1 + 1];
int NR;
char ch[CIFMAX];

void citi()
{
	scanf("%d%d%d%d\n", &N, &M, &W, &H);
	FOR(i, 1, N)
	{
		gets(ch);
		int x = 0;
		for(int k = 0 ; ch[k] && ch[k] != '\n' && ch[k] != EOF ; k++)
			if(ch[k] == ' ')
				c[i].fs = x, x = 0;
			else	x = 10*x + ch[k] - '0';
		c[i].sc = x;
	}
	FOR(i, 1, M)
	{
		gets(ch);
		int x = 0;
		for(int k = 0 ; ch[k] && ch[k] != '\n' && ch[k] != EOF ; k++)
			if(ch[k] == ' ')
				o[i].fs = x, x = 0;
			else	x = 10*x + ch[k] - '0';
		o[i].sc = x;
	}
}

void grupa()
{
	FOR(i, 1, N)//verific cazul cand am coordonate nule
	{
		int x = c[i].fs/W + 1, y = c[i].sc/H + 1;
		if(!(c[i].fs%W))	x--;
		if(!(c[i].sc%H))	y--;
		
		h1[(x*COORDMAX + y)%MOD1].pb(i);
		x++;
		h1[(x*COORDMAX + y)%MOD1].pb(i);
		x--;y++;
		h1[(x*COORDMAX + y)%MOD1].pb(i);
		x++;
		h1[(x*COORDMAX + y)%MOD1].pb(i);
	}
}

void compar(int x, int y, int i)
{
	LL el = (COORDMAX*x + y)%MOD1;
	FORIT(it, h1[el])
		if(c[*it].fs <= o[i].fs && o[i].fs <= c[*it].fs + W && c[*it].sc <= o[i].sc && o[i].sc <= c[*it].sc + H)
		{
			NR++;
			return;
		}
}

void aseza()
{
	FOR(i, 1, M)
	{
		int x = o[i].fs/W + 1, y = o[i].sc/H + 1;
		if(!(o[i].fs%W))	x--;
		if(!(o[i].sc%H))	y--;
		
		compar(x, y, i);
	}
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	grupa();
	aseza();
	printf("%d\n", NR);
	return 0;
}