Cod sursa(job #504313)

Utilizator mgntMarius B mgnt Data 27 noiembrie 2010 13:57:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <algorithm>
using namespace std;

int const maxn=800;
int L[maxn];

int main()
{	ifstream is("nrtri.in");
	ofstream os("nrtri.out");
	int n,i,j,a,b,s,t,p,q,r,c=0;is>>n;
	for(i=0;n>i;++i){is>>L[i];}
	make_heap(L,L+n);
	sort_heap(L,L+n);
	for(i=0;i<n;i++)
	{	for(j=i+1;j<n;j++)
		{	a=L[j]-L[i];b=L[j]+L[i];
			s=-1;p=j+1;r=n-1;
			while(p<=r)
			{	q=(p+r)/2;
				if(L[q]>=a){s=q;r=q-1;}else{p=q+1;}
			}
			t=-1;p=j+1;r=n-1;
			while(p<=r)
			{	q=(p+r)/2;
				if(L[q]<=b){t=q;p=q+1;}else{r=q-1;}
			}
			if((-1!=s)&&(-1!=t))
			{c+=(t-s+1);}
		}
	}
	os<<c<<endl;
	return 0;
}