Cod sursa(job #593908)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 5 iunie 2011 11:41:27
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,v[805];
int sol;

int CautareBinara(int x,int y)
{
	int a,b;
	int st,dr,m;
	a=v[x];
	b=v[y];
	st=y;
	dr=n;
	while(st<=dr)
	{
		m=(st+dr)/2;
		if(m==n || (a+b>=v[m] && a+b<v[m+1]))
			return m;
		else
			if(a+b<v[m])
				dr=m-1;
			else
				st=m+1;
	}
	return -1;
}

int main()
{
	int i,j,poz;
	freopen("nrtri.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",v+i);
	sort(v+1,v+n+1);
	for(i=1;i<n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			poz=CautareBinara(i,j);
			if(poz!=-1)
				sol=sol+poz-j;
		}
	}
	freopen("nrtri.out","w",stdout);
	printf("%d\n",sol);
	return 0;
}