Cod sursa(job #1759320)

Utilizator TincaMateiTinca Matei TincaMatei Data 18 septembrie 2016 21:05:13
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

const int MAX_N = 800;

int v[MAX_N];

void qsort(int begin, int end) {
  int b, e, aux, pivot;
  b = begin;
  e = end;
  pivot = v[(b + e) / 2];
  while(b <= e) {
    while(v[b] < pivot) b++;
    while(v[e] > pivot) e--;
    if(b <= e) {
      aux = v[b];
      v[b] = v[e];
      v[e] = aux;
      b++;
      e--;
    }
  }
  if(b < end)
    qsort(b, end);
  if(begin < e)
    qsort(begin, e);
}

int search(int n, int x) {
  int b, e, mid;
  b = 0;
  e = n;
  while(e - b > 1) {
    mid = (b + e) / 2;
    if(v[mid] <= x)
      b = mid;
    else
      e = mid;
  }
  return b;
}

int main() {
  int n, i, j, sol;
  FILE *fin = fopen("nrtri.in", "r");
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(fin, "%d", &v[i]);
  fclose(fin);

  qsort(0, n - 1);
  sol = 0;
  for(j = 2; j < n; j++)
    for(i = 1; i < j; i++)
      sol = sol + i - search(i + 1, v[j] - v[i]);

  FILE *fout = fopen("nrtri.out", "w");
  fprintf(fout, "%d", sol);
  fclose(fout);
  return 0;
}