Cod sursa(job #565331)

Utilizator katakunaCazacu Alexandru katakuna Data 27 martie 2011 15:55:52
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

#define Nmax 100010

struct punct {
    int x, y;
} H[Nmax], V[Nmax];

int T, n, m, sol;

bool cmpH (punct a, punct b) {

    return a.y > b.y;
}

int main () {

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

    int i, p, xmax, ales;

    scanf ("%d", &T);
    for (; T; T--) {

        sol = 0;
        p = 0, xmax = -1, ales = -1;

        scanf ("%d %d", &n, &m);
        for (i = 1; i <= n; i++)
            scanf ("%d %d", &H[i].x, &H[i].y);
        for (i = 1; i <= m; i++)
            scanf ("%d %d", &V[i].x, &V[i].y);

        sort (H + 1, H + n + 1, cmpH);
        sort (V + 1, V + m + 1, cmpH);

        for (i = 1; i <= n; i++) {
            while (p < m && V[p + 1].y >= H[i].y) {
                if (xmax < V[p + 1].x) xmax = V[p + 1].x;
                p++;
            }

            if (ales < H[i].x)
                ales = xmax, sol++;
        }

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

    return 0;
}