Cod sursa(job #1765363)

Utilizator VasilescuVasilescu Eliza Vasilescu Data 26 septembrie 2016 17:47:50
Problema Pachete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>
int x[50000], y[50000], px[4] = {1, -1, -1, 1}, py[4] = {1, 1, -1, -1};
int ly[50000];

inline int calc(int st, int dr){
  int i, j, pas, d = 0;
  for(i = st; i <= dr; i++){
    j = -1;
    for(pas = (1 << 15); pas > 0; pas >>= 1)
      if(j + pas < d && ly[j + pas] > y[i])
        j += pas;
    j++;
    ly[j] = y[i];
    if(j == d)
      d++;
  }
  return d;
}

void qs(int st, int dr){
  int i = st, j = dr, piv = x[(st + dr) / 2], aux;
  while(i <= j){
    while(x[i] < piv)
      i++;
    while(x[j] > piv)
      j--;
    if(i <= j){
      aux = x[i];  x[i] = x[j];  x[j] = aux;
      aux = y[i];  y[i] = y[j];  y[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  FILE *fin, *fout;
  fin=fopen("pachete.in", "r");
  fout=fopen("pachete.out", "w");
int n, i, xs, ys, j, k;
  fscanf(fin, "%d%d%d", &n, &xs, &ys);
  for(i = 0; i < n; i++){
    fscanf(fin, "%d%d", &x[i], &y[i]);
    x[i] -= xs;
    y[i] -= ys;
  }
  int aux, rez = 0;
  for(k = 0; k < 4; k++){
    for(i = 0; i < n; i++){
      x[i] *= px[k];
      y[i] *= py[k];
    }
    j = n - 1;
    for(i = n - 1; i >= 0; i--){
      if(x[i] > 0 && y[i] > 0){
        aux = x[i];  x[i] = x[j];  x[j] = aux;
        aux = y[i];  y[i] = y[j];  y[j] = aux;
        j--;
      }
    }
    qs(j + 1, n - 1);
    rez += calc(j + 1, n - 1);
    n = j + 1;
    for(i = 0; i < n; i++){
      x[i] *= px[k];
      y[i] *= py[k];
    }
  }
  fprintf(fout, "%d", rez);
  fclose(fout);
  fclose(fin);
  return 0;
}