Cod sursa(job #554480)

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

#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;
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--;
		
		loc.insert(mp(mp(x, y), i));
		x++;
		loc.insert(mp(mp(x, y), i));
		x--;y++;
		loc.insert(mp(mp(x, y), i));
		x++;
		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[it->second].fs <= o[i].fs && o[i].fs <= c[it->second].fs + W && c[it->second].sc <= o[i].sc && o[i].sc <= c[it->second].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;
}