Cod sursa(job #630336)

Utilizator George25Raduta George Cristian George25 Data 5 noiembrie 2011 12:15:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

int i,n,a[801],k,j,nr,s1,poz;

inline void cautbinar(int sum, int pos){
	int st,mij,dr;
	st=pos;
	dr=n;
	mij=(st+dr)/2;
	while (st<dr)
	{
		if (a[mij]==sum)
		{
			poz=mij;
			break;
		}
		else if (a[mij]>sum)
		{
			dr=mij-1;
			mij=(st+dr)/2;
		}
		else if (a[mij]<sum)
		{
			poz=mij;
			st=mij+1;
			mij=(st+dr)/2;
		}
	}
}

int main(){
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; ++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for (i=1; i<=n-2; ++i)
	{
		for (j=i+1; j<=n-1; ++j)
		{
			s1=a[i]+a[j];
			k=j+1;
			poz=-1;
			if (s1>=a[n])
			{
				nr=nr+n-j;
			}
			else
			{
				cautbinar(s1,k);
				if (poz>0) nr=nr+poz-j;
			}
		}
	}
	printf("%d",nr);
	return(0);
}