Cod sursa(job #132017)

Utilizator floringh06Florin Ghesu floringh06 Data 4 februarie 2008 21:18:06
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define FIN "hvrays.in"
#define FOUT "hvrays.out"
#define MAX_N 100010

typedef struct 
{
        int x, y;
} point;

point A[MAX_N];
point B[MAX_N];
int H, V, x, y, i;
int T;

      struct function
      {
             bool operator () (const point &x, const point &y) const
             {
                  if (x.y > y.y) 
                     return 1;
                  if (x.y == y.y && x.x > y.x)
                     return 1;
                  return 0;
             }
      };

      void solve ()
      {
           sort (A, A + H, function());
           sort (B, B + V, function());
           int best, h;
           int a, b;
           
           while (a < H)
           {
                 b = h + 1;
                 for (; A[a].x <= A[h].x && a <= H;) ++a;
                 for (; B[b].y >= A[a].y && b <= V;)
                 {
                     if (B[b].x > B[h].x) h = b; ++b;
                 }
           }
      }

      int main ()
      {
          freopen (FIN, "r", stdin);
          freopen (FOUT, "w", stdout);
          
          scanf ("%d", &T);
          while (T)
          {
                scanf ("%d %d", &H, &V);
                for (i = 0; i < H; ++i) scanf ("%d %d", &A[i].x, &A[i].y);
                for (i = 0; i < V; ++i) scanf ("%d %d", &B[i].x, &B[i].y);
                
           sort (A, A + H, function());
           sort (B, B + V, function());
           int best, h;
           int a, b;
           best = h = 0;
           a = b = 0;
           
           while (a < H)
           {
                 b = h + 1;
          
                 while (B[b].y >= A[a].y && b < V)
                 {
                     if (B[b].x > B[h].x) h = b;
                     ++b;
                 }
                 while (A[a].x <= A[h].x && a < H)
                     ++a;
                 ++best;
           }
           printf ("%d\n", best);
           --T;
          }
          
          return 0;
      }