Cod sursa(job #1289721)

Utilizator RaduVisanRadu Visan RaduVisan Data 10 decembrie 2014 11:04:47
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
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;
    }
};

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

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

        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);
    }
}