Cod sursa(job #351408)

Utilizator ProtomanAndrei Purice Protoman Data 27 septembrie 2009 22:58:45
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <set>

#define MAX 100010
#define mp make_pair
#define x first
#define y second

using namespace std;

int n, m, w, h, sol;
multiset <pair<int, int> > msetOgr;
pair <int, int> coOi[MAX], coOgr[MAX];

int main()
{
	ifstream cin("ograzi.in");
	ofstream cout("ograzi.out");

	cin >> n >> m >> w >> h;
	
	for (int i = 1; i <= n; i++)
		cin >> coOgr[i].x >> coOgr[i].y;

	for (int i = 1; i <= m; i++)
		cin >> coOi[i].x >> coOi[i].y;

	sort(coOi + 1, coOi + 1 + m);
	sort(coOgr + 1, coOgr + 1 + n);

	int acOi = 1, acOgr = 1, fOgr = 1;

	for (int i = 0; i <= 1000000; i++)
	{
		for (; coOgr[acOgr].x == i && acOgr <= n; acOgr++)
			msetOgr.insert(mp(coOgr[acOgr].y + h, acOgr));
		for (; coOgr[fOgr].x < i - w && fOgr <= n; fOgr++)
			msetOgr.erase(mp(coOgr[fOgr].y + h, fOgr));

		for (; coOi[acOi].x == i && acOi <= m; acOi++)
			if (msetOgr.lower_bound(mp(coOi[acOi].y, 0)) != msetOgr.end())
				if ((*msetOgr.lower_bound(mp(coOi[acOi].y, 0))).x <= coOi[acOi].y + h)
					sol++;
	}

	cout << sol;

	return 0;
}