Cod sursa(job #457216)

Utilizator SmarandaMaria Pandele Smaranda Data 18 mai 2010 16:46:43
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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)
			st=m+1;
		else
		{
			
			dr=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);
			if (m1!=m2 && m1!=i  && m1!=j && v[m1]<=s1)
				num=num+1;
			if (m1!=m2 && m2!=i && m2!=j  && v[m2]>=s2)
				num=num+1;
		}
	//num=num/3;
	printf("%ld\n",num);
	return 0;
}