Cod sursa(job #848844)

Utilizator stoicatheoFlirk Navok stoicatheo Data 5 ianuarie 2013 20:01:15
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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;
}