Cod sursa(job #211031)

Utilizator kiaraFugaru Sabina kiara Data 30 septembrie 2008 13:47:05
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 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,j=2;j<=n;i++,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;
}