Cod sursa(job #448912)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 4 mai 2010 22:56:35
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define N 100000

class punct
{
public:
	int x, y;
};

int h, v;
punct hr[N], vr[N];

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

int fcmp(const void* a, const void* b)
{
	punct pa, pb;
	pa = *((punct*)a);
	pb = *((punct*)b);
	if(pa.x < pb.x) return 1;
	if(pa.x > pb.x) return -1;
	if(pa.y > pb.y) return 1;
	return -1;
}

void printvect(punct vect[], int ne)
{
	int i;
	printf("{");
	for(i = 0; i < ne; ++i)
		printf(" (%d, %d) ", vect[i].x, vect[i].y);
	printf("}\n");
}


int idh, idv;
void pas()
{
	int fx = hr[idh].x, fy = hr[idh].y;
	//caut prima raza verticala care trece prin chestia asta
	while(1)
	{
		if(vr[idv].x >= fx && vr[idv].y >= fy) break;
		idv++;
	}
//	printf(":idv = %d\n", idv);
	//caut prima raza verticala care nu trece prin chestia asta
	while(1)
	{
		if(idv == v) return;
		if(!(vr[idv].x >= fx && vr[idv].y >= fy)) break;
		idv++;
	}
//	printf(":idv = %d\n", idv);
	//ma intorc un pas
	idv--;
	fx = vr[idv].x;
	fy = vr[idv].y;
//	printf(":fy = %d\n", fy);
	//caut prima raza orizontala care nu trece prin raza verticala gasita
	while(1)
	{
		if(idh == h) return;
		if(hr[idh].y > fy) break;
		idh++;
	}
}

int main()
{
	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);
	int t, i;
	int cs; // cardinal submultime
	scanf("%d", &t);
	while(t--)
	{
		//citire
		scanf("%d%d", &h, &v);
		for(i = 0; i < h; ++i) scanf("%d%d", &hr[i].x, &hr[i].y);
		for(i = 0; i < v; ++i) scanf("%d%d", &vr[i].x, &vr[i].y);
		
		//sortare
//		qsort(hr, h, sizeof(punct), fcmp);
//		qsort(vr, v, sizeof(punct), fcmp);
		
		sort(hr, hr + h, cmp);
		sort(vr, vr + v, cmp);

//		printvect(hr, h);
//		printvect(vr, v);
		//rezolvare
		cs = 0;
		idh = 0;
		idv = 0;
		while(idh < h && idv < v)
		{
			cs++;
			pas();
		//	printf("idh = %d, idv = %d\n", idh, idv);
		}
		printf("%d\n", cs);
	}
	return 0;
}