Cod sursa(job #457199)

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

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


int main()
{
	long i,j,s1,s2,m1,m2,num=0;
	
	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!=i && m1!=j && m1<=n && m1>=0 && v[m1]<=s1)
				
					num++;
					
				
			if (m2!=i && m2!=j && m2<=n && m2>=0 && v[m2]<=s2)
				
					num++;
					
			
		}
	printf("%ld\n",num);
	return 0;
}