Cod sursa(job #362750)

Utilizator bog29Antohi Bogdan bog29 Data 10 noiembrie 2009 21:13:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#define dmax 803
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n,x[dmax],sol;
int sf(const void *a,const void *b)
{	return ( *(int*)a - *(int*)b );
}
int bs(int l,int r,int i,int j)
{	int m;
	//out<<l<<" "<<r<<'\n';
	if(r==0)
	{	if(x[0]+x[j]>=x[i])	return 0;
		else return j;
	}
	while(l<r)
	{	m=(l+r)/2;
		if(r-l==1)
		{	if(x[l]+x[j]>=x[i])	
				return l;
			else if(x[r]+x[j]>=x[i])	
				return r;
			else return j;
		}	
		if(x[m]+x[j]==x[i])
		{	while(x[m-1]+x[j]==x[i])
				m--;
			return m;
		}	
		else if(x[m]+x[j]>x[i])
			r=m;
		else if(x[m]+x[j]<x[i])
			l=m;
	}
}
int main()
{	int i,j,q;
	in>>n;
	for(i=0;i<n;i++)
		in>>x[i];
	in.close();
	qsort( (void*)x,n,sizeof(x[0]),sf);
	for(i=n-1;i>1;i--)
		for(j=i-1;j>0;j--)	
		{	//out<<i<<" "<<j<<" "<<q<<" "<<j-q<<'\n';
			q=bs(0,j-1,i,j);
			sol=sol+j-q;
		}	
	out<<sol;
	out.close();
	return 0;
}