Cod sursa(job #268306)

Utilizator vlad_olteanVladimir Oltean vlad_oltean Data 1 martie 2009 00:56:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>

int n,v[801];

int poz(int l,int r)
{	int d=0,t;
	while(l<r)
	{	if(v[l]>v[r])
		{	t=v[l]; v[l]=v[r]; v[r]=t;
			d=1-d;
		}
		l+=d;r-=1-d;
	}
	return l;
}

void qsort(int l,int r)
{	int k;
	if(l<r)
	{	k=poz(l,r);
		qsort(l,k-1);
		qsort(k+1,r);
	}
}

int search(int l,int r, int c)
{	int m;
	while(l<r)
	{
		m=l+(r-l+1)/2;
		if(v[m]<=c) l=m;
		else r=m-1;
	}
	return l;
}

int main()
{
	int k,nrtri=0;
	
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	qsort(1,n);
	
	for(int i=1;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{	
			k=search(j+1,n,v[i]+v[j]);
			if(v[k]<=v[i]+v[j]) nrtri+=(k-j);
		}
	
	printf("%d",nrtri);
	return 0;
}