Cod sursa(job #96513)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 1 noiembrie 2007 22:36:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
int v[801],n,i,j,s=0,k;
/*int cauta(int n,int k,int b){
	int p,u,m;
	p=b+1;u=n-1;
	if (p==u){
		if (v[p]>=k)
			return n-1;
		else return n;
	}
	while (p<=u){
		m=(p+u)/2;
		if (k==v[m])
			return m;
		if(v[m]<k)
			p=m;
		else
			u=m+1;
	}
	//if(v[u]>n)
		//return p-1;
	//printf("%d ",u);
	return u;//p
}
*/
int cautare(int p, int u)
{
  int m;
  m=(p+u)/2;
  while (p<=u){
      if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n))
		  return m;
	  else if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j]) {p=m+1; m=(p+u)/2;}
	  else {
		  u=m-1; 
		  m=(p+u)/2;
		  }  
  }
  return 0;
}
int compara (const void * a, const void * b){
  return ( *(int*)a - *(int*)b );
}
int main(){
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<n+1;++i)
		scanf("%d",&v[i]);
	qsort (v, n+1, sizeof(int), compara);
	for (i=1; i<n-1; ++i)    
		for (j=i+1; j<n; ++j){
			k=cautare(j+1,n);
			if (k) s+=(k-j);
		}
	printf("%d\n",s);
	return 0;
}