Cod sursa(job #1289725)

Utilizator RaduVisanRadu Visan RaduVisan Data 10 decembrie 2014 11:06:52
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype>
using namespace std;

const int NMAX = 100010;

int T, N, M;
struct HV
{
    int X, Y;
}H[NMAX], V[NMAX];

struct Comp
{
    bool operator() (const HV &A, const HV &B) const
    {
        return A.X > B.X;
    }
};

const int MaxB = 8192;
char Buf[MaxB];
int Ptr;

int Get()
{
    int Nr = 0;
    while(!isdigit(Buf[Ptr]))
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]))
    {
        Nr = Nr * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Nr;
}

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

    T = Get();
    for(; T; T --)
    {
        N = Get(); M = Get();
        for(int i = 1; i <= N; ++ i) H[i].X = Get(), H[i].Y = Get();
        for(int i = 1; i <= M; ++ i) V[i].X = Get(), V[i].Y = Get();

        sort(H + 1, H + N + 1, Comp());
        sort(V + 1, V + M + 1, Comp());

        int MaxY = 0, Ans = 0;
        for(int i = 1, j = 1; i <= N; ++ i)
        {
            if(H[i].Y <= MaxY) continue;
            Ans ++;
            while(j <= M && V[j].X >= V[i].X)
                MaxY = max(MaxY, V[j].Y), j ++;
        }

        printf("%i\n", Ans);
    }
}