Cod sursa(job #2155618)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 7 martie 2018 22:53:46
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 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;
}