Cod sursa(job #457188)

Utilizator cahemanCasian Patrascanu caheman Data 18 mai 2010 16:11:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<algorithm>
int b[100];
using namespace std;
int main()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int c=0,a,d,i,j,n,m,u,p,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&b[i]);
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
	for(j=i+1;j<=n;j++)
	{
		u=n;
		p=1;
		x=b[i]+b[j];
		y=b[j]-b[i];
		while(u>=p)
		{
			m=(u+p)/2;
			if(b[m]<=x&&y>=b[m])
				u=m-1;
			else
				p=m+1;
		}
		a=m;
		u=n;
		p=1;
		while(u>=p)
		{
			m=(u+p)/2;
			if(b[m]<x&&y>=b[m])
				u=m-1;
			else
				p=m+1;
		}
		d=m;
		if(d>=a&&a!=0&&d!=n+1)
		c=c+d-a+1;
	}
printf("%d",c);
return 0;
}