Cod sursa(job #1740189)

Utilizator cella.florescuCella Florescu cella.florescu Data 11 august 2016 09:51:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
int v[2000];

void myqsort(int be, int en){
  int aux, b=be, e=en, pivot=v[be+rand()%(en-be+1)];
  while(b<=e){
    while(pivot>v[b])
      ++b;
    while(pivot<v[e])
      --e;
    if(b<=e){
      aux=v[b]; v[b]=v[e]; v[e]=aux;
      ++b; --e;
    }
  }
  if(be<e)
    myqsort(be, e);
  if(b<en)
    myqsort(b, en);
}

int main()
{
    FILE *fin, *fout;
    int n, i, j, k, tri;
    fin=fopen("nrtri.in", "r");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++)
      fscanf(fin, "%d", &v[i]);
    fclose(fin);
    myqsort(0, n-1);
    tri=0;
    for(i=0; i<n-2; i++){
      k=i+2;
      for(j=i+1; j<n-1; j++){
        if(k==j)
          ++k;
        while(k<n && v[i]+v[j]>=v[k])
          ++k;
        tri+=k-j-1;
      }
    }
    fout=fopen("nrtri.out", "w");
    fprintf(fout, "%d\n", tri);
    fclose(fout);
    return 0;
}