Cod sursa(job #62667)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 23 mai 2007 18:40:12
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream.h>
#include<math.h>
int n,i,j,v[801];
int cauta()
	{
	int st,dr;
	st=1;
	dr=n;
	while(st<dr)
		{
		if(v[(st+dr)/2]>=abs(v[i]-v[j])&&v[(st+dr)/2]<=v[i]+v[j])
				return (st+dr)/2;
		if(v[(st+dr)/2]<=abs(v[i]-v[j]))st=(st+dr)/2+1;
		else dr=(st+dr)/2-1;
		}
	return 0;
	}
int main()
{
int cnt=0,x;
ifstream in("nrtri.in");
in>>n;
for(i=1;i<=n;i++)
	in>>v[i];
in.close();
int aux;
for(i=1;i<n;i++)
	for(j=i+1;j<=n;j++)
		if(v[i]>v[j])
			{
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			}
for(i=1;i<n;i++)
	for(j=i+1;j<=n;j++)
		{
		x=cauta();
		if(x!=0)
			{
			for(int tz=x;tz<=n;tz++)
				{
				if(v[i]+v[j]<v[tz])
					break;
				if(i==tz||j==tz)
					cnt--;
				//if(i!=tz&&j!=tz)cnt++//cout<<"SUS : "<<v[i]<<" "<<v[j]<<" "<<v[tz]<<endl;
				}
			cnt+=tz-x;
			for(tz=x-1;tz>0;tz--)
				{
				if(abs(v[i]-v[j])>v[tz])
					break;
				if(i==tz||j==tz)
					cnt--;

				//if(i!=tz&&j!=tz)cnt++//cout<<"JOS : "<<v[i]<<" "<<v[j]<<" "<<v[tz]<<endl;
				}
			cnt+=x-tz-1;
			}
		}
//cout<<"-------------------------------------------------"<<endl;
ofstream out("nrtri.out");
out<<cnt/3<<"\n";
out.close();
return 0;
}