Cod sursa(job #1428852)

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

inline char cmp(int x1, int t1, int x2, 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 + rand() % (dr - st + 1), pivx = x[point[m]], pivt = tip[point[m]], aux;
  while(i <= j){
    while(cmp(x[point[i]], tip[point[i]], pivx, pivt))
      i++;
    while(cmp(pivx, pivt, x[point[j]], tip[point[j]]))
      j--;
    if(i <= j){
      aux = point[i];  point[i] = point[j];  point[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  srand(time(NULL));
  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;
      point[i] = i;
    }
    for(i = 0; i < v; i++){
      fscanf(in, "%d%d", &x[i + h], &y[i + h]);
      tip[i + h] = 1;
      point[i + h] = i + h;
    }
    l = h + v;
    qs(0, l - 1);
    rez = 0;
    hmcrt = hmpsb = -1;
    for(i = 0; i < l; i++){
      if(tip[point[i]] == 1 && hmpsb < y[point[i]])
        hmpsb = y[point[i]];
      if(tip[point[i]] == 0 && y[point[i]] > hmcrt){
        hmcrt = hmpsb;
        rez++;
      }
    }
    fprintf(out, "%d\n", rez);
  }
  fclose(in);
  fclose(out);
  return 0;
}