Cod sursa(job #505749)

Utilizator bogdanrus2010Rus Bogdan bogdanrus2010 Data 3 decembrie 2010 20:25:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 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);
	for(i=0;i<n;i++) 
	sort_heap(L,L+n);
	{
		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;
}