Pagini recente » Cod sursa (job #63571) | Cod sursa (job #44151) | Cod sursa (job #561209) | Cod sursa (job #2360295) | Cod sursa (job #92697)
Cod sursa(job #92697)
#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;
}