Cod sursa(job #554382)

Utilizator ooctavTuchila Octavian ooctav Data 14 martie 2011 20:14:10
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 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;

#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];
multimap<PII, int> loc;
int NR;

void citi()
{
	scanf("%d%d%d%d", &N, &M, &W, &H);
	FOR(i, 1, N)
		scanf("%d%d", &c[i].fs, &c[i].sc);
	FOR(i, 1, M)
		scanf("%d%d", &o[i].fs, &o[i].sc);
}

void grupa()
{
	FOR(i, 1, M)//verific cazul cand am coordonate nule
	{
		int x, y;
		if(o[i].fs % W == 0)	x = o[i].fs/W;
		else	x = o[i].fs/W + 1;
		
		if(o[i].sc % H == 0)	y = o[i].sc/H;
		else	y = o[i].sc/H + 1;
		
		loc.insert(mp(mp(x, y), i));
	}
}

void compar(int x, int y, int i)
{
	multimap<PII, int> :: iterator it;
	for(it = loc.equal_range(mp(x, y)).fs ; it != loc.equal_range(mp(x, y)).sc ; it++)
		if(c[i].fs <= o[it->second].fs && o[it->second].fs <= c[i].fs + W && c[i].sc <= o[it->second].sc && o[it->second].sc <= c[i].sc + H)
			NR++;
}

void aseza()
{
	FOR(i, 1, N)
	{
		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--;
		
		compar(x, y, i);
		x++;
		compar(x, y, i);
		x--;y++;
		compar(x, y, i);
		x++;
		compar(x, y, i);
	}
}

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