Cod sursa(job #448920)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 4 mai 2010 23:11:49
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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;
}

inline int maxim(int a, int b)
{
	if(a > b) return a;
	return b;
}

int main()
{
	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);
	int t, i, idv, coltx;
	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);
		
		sort(hr, hr + h, cmp);
		sort(vr, vr + v, cmp);
		
		coltx = -1;
		cs = 0;
		idv = 0;

		for(i = 0; i < h; ++i) //pentru fiecare raza orizontala
		{
			if(hr[i].x > coltx)
			{
				cs++;
				while(idv < v && hr[i].y <= vr[idv].y)
				{
					coltx = maxim(coltx, vr[idv].x);
					idv++;
				}
			}
		}

		printf("%d\n", cs);
	}
	return 0;
}