Cod sursa(job #629059)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 2 noiembrie 2011 16:49:32
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<stdio.h>
#include<algorithm>


using namespace std;


int a[810];



int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int n,i,j,st,dr,m,nr=0,x;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(i=1;i<=n;++i)
		for(j=i+1;j<=n;++j)
		{
			x=a[i]+a[j];
			dr=n;
			st=j+1;
			while(st<=dr)
			{
				m=st+(dr-st)/2;
				if(a[m]<=x)
				{
					++nr;
					st=m+1;
				}
				else
					dr=m-1;
			}
		}
	printf("%d\n",nr);
	return 0;
}