Cod sursa(job #341755)

Utilizator ProtomanAndrei Purice Protoman Data 19 august 2009 14:18:57
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <algorithm>
#include <stdio.h>

#define MAX 100010

using namespace std;

struct coord
{
	int x, y;
};
coord hor[MAX], ver[MAX];
int t, h, v;
char buffIn[32];

inline bool cmp(const coord &a, const coord &b)
{
	if (a.y == b.y)
		return (a.x > b.x);
	return (a.y > b.y);
}

int main()
{
	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);

	for (scanf("%d\n", &t); t; t--)
	{
		scanf("%d %d\n", &h, &v);

		for (int i = 1; i <= h; i++)
		{
			fgets(buffIn, 32, stdin);
			sscanf(buffIn, "%d %d", &hor[i].x, &hor[i].y);
		}
		for (int i = 1; i <= v; i++)
		{
			fgets(buffIn, 32, stdin);
			sscanf(buffIn, "%d %d", &ver[i].x, &ver[i].y);
		}

		sort(hor + 1, hor + 1 + h, cmp);
		sort(ver + 1, ver + 1 + v, cmp);

		int sel = 0, maxX = 0;
		for (int rmh = 1, rmv = 1; rmh <= v; sel++)
		{
			int primGs = hor[rmh].y;

			for (; rmv <= h && ver[rmv].y >= primGs; rmv++)
				maxX = max(maxX, ver[rmv].x);

			for (; rmh <= v && hor[rmh].x <= maxX; rmh++);
		}

		printf("%d\n", sel);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}