Pagini recente » Cod sursa (job #2989737) | Cod sursa (job #259271) | Cod sursa (job #361609) | Cod sursa (job #1103685) | Cod sursa (job #90412)
Cod sursa(job #90412)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define HORIZ 0
#define VERT 1
#define INF 666666666
#define NMAX 100100
int i, j, k, H, Hnew, V, nv, ymax, xmax;
int xh[NMAX], yh[NMAX], xv[NMAX], yv[NMAX];
int main()
{
int te, T;
freopen("hvrays.in", "r", stdin);
freopen("hvrays.out", "w", stdout);
scanf("%d", &T);
for (te = 1; te <= T; te++)
{
scanf("%d %d", &H, &V);
for (i = 1; i <= H; i++)
{
scanf("%d %d", &xh[i], &yh[i]);
if (xh[i] < 0 || xh[i] > 50000000 || yh[i] < 0 || yh[i] > 50000000)
fprintf(stderr, "bug?\n");
}
for (i = 1; i <= V; i++)
{
scanf("%d %d", &xv[i], &yv[i]);
if (xv[i] < 0 || xv[i] > 50000000 || yv[i] < 0 || yv[i] > 50000000)
fprintf(stderr, "bug?\n");
}
nv = 0;
while (H > 0 && V > 0)
{
ymax = -1;
for (i = 1; i <= H; i++)
if (yh[i] > ymax)
ymax = yh[i];
xmax = -1;
for (i = 1; i <= V; i++)
if (yv[i] >= ymax && xv[i] >= xmax)
xmax = xv[i],
k = i;
if (xmax < 0)
break;
nv++;
Hnew = 0;
for (j = 1; j <= H; j++)
if (!(xh[j] <= xv[k] && yh[j] <= yv[k]))
{
Hnew++;
xh[Hnew] = xh[j];
yh[Hnew] = yh[j];
}
H = Hnew;
for (i = k + 1; i <= V; i++)
{
xv[i - 1] = xv[i];
yv[i - 1] = yv[i];
}
V--;
}
if (H > 0)
nv = -1;
printf("%d\n", nv);
fprintf(stderr, "-> Sol=%d [Hleft=%d; Vleft=%d]\n", nv, H, V);
}
return 0;
}