Cod sursa(job #211211)

Utilizator kiaraFugaru Sabina kiara Data 1 octombrie 2008 12:41:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>   
#include<stdlib.h>   
int compare (const void * a, const void * b){   
  return ( *(int*)a - *(int*)b );   
}   
int cauta2( int *v, int p, int u, int x){   
 if(p==u){   
  while(v[p]<=x)  
	  p++;
   return p;   
 }   
 if(x<=v[(p+u)/2])   
  return cauta2(v,p,(p+u)/2,x);   
 return cauta2(v,(p+u)/2+1,u,x);   
}   
int main(){   
    int v[100000],n,i,j,k,suma=0,h,poz;   
    freopen("nrtri.in","r",stdin);   
    freopen("nrtri.out","w",stdout);   
    scanf("%d",&n);   
    for(i=1;i<=n;i++){   
        scanf("%d",&v[i]);   
    }   
    qsort (v+1, n, sizeof(int), compare);   
    for(i=1;i<=n;i++){   
        for(j=i+1;j<=n;j++){   
        k=v[i]+v[j];   
        poz=j+1;   
        h=cauta2(v,1,n,k);   
        suma=suma+(h-poz+1);   
    }   
    }   
    printf("%d",suma);   
    return 0;   
}