Cod sursa(job #1885596)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 20 februarie 2017 09:23:37
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 100050

using namespace std;

struct coord
{
    int x, y;
    bool operator>(const coord &e) const
    {
        return y > e.y;
    }
};
int t, h, v;
coord hes[MAXN], ves[MAXN];

void read()
{
    scanf("%d %d", &h, &v);
    for (int i = 1; i <= h; i++)
        scanf("%d %d", &hes[i].x, &hes[i].y);
    for (int i = 1; i <= v; i++)
        scanf("%d %d", &ves[i].x, &ves[i].y);
}

void solve()
{
    sort(hes+1, hes+h+1, greater<coord>());
    sort(ves+1, ves+v+1, greater<coord>());
    int xmax = -1, xcrt = -1, sol = 0;
    for (int i = 1, j = 1; i <= h; i++)
    {
        for (j; j <= v && ves[j].y >= hes[i].y; j++)
            xmax = max(xmax, ves[j].x);
        if (hes[i].x > xcrt) {
            sol++;
            xcrt = xmax;
        }
    }
    printf("%d\n", sol);
}

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

    scanf("%d", &t);
    while (t--) {
        read();
        solve();
    }

    return 0;
}