Cod sursa(job #457220)

Utilizator SmarandaMaria Pandele Smaranda Data 18 mai 2010 16:49:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<algorithm>
using namespace std; 
long n;
long k[4];
long v[801];
long cautbin1 (long x )
{
	long m,dr,st;
	st=1;
	dr=n;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (v[m]<=x)
			st=m+1;
		else
			dr=m-1;
			
	}
	k[1]=st;
	return dr;
}

long cautbin2 (long x)
{
	long m , aux ,st,dr;
	dr=n;st=1;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (v[m]>=x)
			dr=m-1;
		else
		{
			
			st=m+1;
		}
	}
	k[2]=dr;
	return st;
}


int main()
{
	long i,j,s1,s2,m1,m2,num=0,k1,k2;
	
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	sort(v+1,v+n+1);
	for (i=1;i<n;i++)
		
		for (j=i+1;j<=n;j++)
		{
			s1=v[i]+v[j];
			s2=v[j]-v[i];
			m2=cautbin2(s2);
			m1=cautbin1(s1);
			num+=(k[1]-k[2]+1);
			if (v[i]>=v[k[2]+1])
				num--;
			if (v[j]>=v[k[2]+1])
				num--;
		}
	num=num/3;
	printf("%ld\n",num/3);
	return 0;
}