Cod sursa(job #210598)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 28 septembrie 2008 10:05:59
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#define N 807
int n,v[N],i,j,nr;
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-1))
			return m-j;
		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;
}

void sort(){
	int x,min;
	for(i=0;i<n-1;++i){
		min=i;
		for(j=i+1;j<n;++j)
			if(v[j]>v[min])
				min=j;
		if(min!=i){
			x=v[min];
			v[min]=v[i];
			v[i]=x;
		}
	}
}
int main(){
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;++i)
		scanf("%d",&v[i]);
	for(i=0;i<n-2;++i)
		for(j=i+1;j<n-1;++j)
			nr+=cautare(1,n);
	printf("%d\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}