Cod sursa(job #92697)

Utilizator filipbFilip Cristian Buruiana filipb Data 16 octombrie 2007 16:23:01
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxim(a, b) ((a > b) ? a : b)
#define INF 2000000001
#define x first
#define y second
#define NMax 100005

int Max[NMax];
pair<int, int> HH[NMax], VV[NMax], hor[NMax], ver[NMax], I[NMax];

int cmp_h(const pair<int, int>& a, const pair<int, int>& b)
{
    return (a.y > b.y) || (a.y == b.y && a.x > b.x);
}

int cmp_v(const pair<int, int>& a, const pair<int, int>& b)
{
    return (a.x < b.x) || (a.x == b.x && a.y > b.y);
}


int main(void)
{
    int T, H, V, i, j, cnt = 0;
    
    freopen("hvrays.in", "r", stdin);
    freopen("hvrays.out", "w", stdout);

    for (scanf("%d", &T); T; T--)
    {
        scanf("%d %d", &H, &V);
        for (i = 1; i <= H; i++)
            scanf("%d %d", &HH[i].x, &HH[i].y);
        for (i = 1; i <= V; i++)
            scanf("%d %d", &VV[i].x, &VV[i].y);

        sort(HH+1, HH+H+1, cmp_h);
        sort(VV+1, VV+V+1, cmp_v);

        for (i = 1, j = 0; i <= H; i++)
            if (!j || HH[i].x > hor[j].x && HH[i].y < hor[j].y)
                hor[++j] = HH[i];
        H = j;

        for (i = 1, j = 0; i <= V; i++)
            if (!j || VV[i].x > ver[j].x && VV[i].y < ver[j].y)
                ver[++j] = VV[i];
        V = j;

        hor[0].y = INF; hor[0].x = -INF;

        for (i = 1; i <= V; i++)
        {
            I[i].x = I[i-1].x;
            while (hor[I[i].x].y > ver[i].y || hor[I[i].x].x > ver[i].x && I[i].x <= H)
                I[i].x++;
            I[i].y = maxim(I[i].x, I[i-1].y);
            while (hor[I[i].y].y <= ver[i].y && hor[I[i].y].x <= ver[i].x && I[i].y <= V)
                I[i].y++;
            I[i].y--;
        }

        for (i = 1, j = 1; i <= V; i++)
        {
            while (i == I[j].x)
                Max[i] = maxim(Max[i], I[j].y),
                j++;
        }

        for (i = 2; i <= V; i++)
            Max[i] = maxim(Max[i], Max[i-1]);

        cnt = 0; i = 1;
        while (i < V)
            i = Max[i], cnt++;

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

    return 0;
}