Cod sursa(job #351409)

Utilizator ProtomanAndrei Purice Protoman Data 27 septembrie 2009 23:03:07
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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 <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(coOgr[acOgr].y + h);
		for (; coOgr[fOgr].x < i - w && fOgr <= n; fOgr++)
			msetOgr.erase(msetOgr.find(coOgr[fOgr].y + h));

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

	cout << sol;

	return 0;
}