Cod sursa(job #1428845)

Utilizator hrazvanHarsan Razvan hrazvan Data 5 mai 2015 10:33:23
Problema Hvrays Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#define MAXL 200000
int x[MAXL], y[MAXL];
char tip[MAXL];

inline void intersch(int i, int j){
  int aux;
  aux = x[i];  x[i] = x[j];  x[j] = aux;
  aux = y[i];  y[i] = y[j];  y[j] = aux;
  aux = tip[i];  tip[i] = tip[j];  tip[j] = aux;
}

inline char cmp(int x1, int y1, int t1, int x2, int y2, int t2){
  if(x1 > x2)
    return 1;
  if(x2 > x1)
    return 0;
  if(t1 > t2)
    return 1;
  if(t2 > t1)
    return 0;
  return 0;
}

void qs(int st, int dr){
  int i = st, j = dr, m = (st + dr) / 2, pivx = x[m], pivy = y[m], pivt = tip[m];
  while(i <= j){
    while(cmp(x[i], y[i], tip[i], pivx, pivy, pivt))
      i++;
    while(cmp(pivx, pivy, pivt, x[j], y[j], tip[j]))
      j--;
    if(i <= j){
      intersch(i, j);
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  FILE *in = fopen("hvrays.in", "r");
  FILE *out = fopen("hvrays.out", "w");
  int t, h, v, i, l, hmcrt, hmpsb, rez;
  fscanf(in, "%d", &t);
  for(; t > 0; t--){
    fscanf(in, "%d%d", &h, &v);
    for(i = 0; i < h; i++){
      fscanf(in, "%d%d", &x[i], &y[i]);
      tip[i] = 0;
    }
    for(i = 0; i < v; i++){
      fscanf(in, "%d%d", &x[i + h], &y[i + h]);
      tip[i + h] = 1;
    }
    l = h + v;
    qs(0, l - 1);
    rez = 0;
    hmcrt = hmpsb = -1;
    for(i = 0; i < l; i++){
      if(tip[i] == 1 && hmpsb < y[i])
        hmpsb = y[i];
      if(tip[i] == 0 && y[i] > hmcrt){
        hmcrt = hmpsb;
        rez++;
      }
    }
    fprintf(out, "%d\n", rez);
  }
  fclose(in);
  fclose(out);
  return 0;
}