Cod sursa(job #211218)

Utilizator kiaraFugaru Sabina kiara Data 1 octombrie 2008 13:01:48
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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){   
	 if(v[p]<=x)
		 return p;
	 else
		 return p-1;
 }   
 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-1;i++){   
        for(j=i+1;j<n;j++){   
        k=v[i]+v[j];   
        poz=j+1;   
        h=cauta2(v,1,n,k);
		while(v[h]<=k&&h<n){
			h++;
		}
		
        suma=suma+(h-poz);   
    }   
    }   
    printf("%d",suma);   
    return 0;   
}