Cod sursa(job #739396)

Utilizator geniucosOncescu Costin geniucos Data 22 aprilie 2012 22:19:18
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int v,p,u,m,i,j,nr,sf,in,n,a[802];
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;i++)
	for(j=i+1;j<=n;j++)
	{
		p=1;
		u=n;
		while(p<=u)
		{
			m=(p+u)/2;
			if(a[m]>a[i]+a[j]) u=m-1;
			else
			if(a[m]<a[i]+a[j]) p=m+1;
			else break;
		}
		if(p<=u)
		{
			sf=m;
			while(a[sf]==a[i]+a[j]) sf++;
			sf--;
		}
		else sf=p-1;
		///////////////////////////////////////
		p=1;
		u=n;
		v=max(a[i]-a[j],a[j]-a[i]);
		while(p<=u)
		{
			m=(p+u)/2;
			if(a[m]>v) u=m-1;
			else
			if(a[m]<v) p=m+1;
			else break;
		}
		if(p<=u)
		{
			in=m;
			while(a[in]==v) in--;
			in++;
		}
		else in=p;
		if(in<j+1) in=j+1;
		nr=nr+sf-in+1;
	}
printf("%d\n",nr);
return 0;
}