Cod sursa(job #62669)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 23 mai 2007 18:41:39
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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 tzi=x;tzi<=n;tzi++)
				{
				if(v[i]+v[j]<v[tzi])
					break;
				if(i==tzi||j==tzi)
					cnt--;
				}
			cnt+=tzi-x;
			for(tzi=x-1;tzi>0;tzi--)
				{
				if(abs(v[i]-v[j])>v[tzi])
					break;
				if(i==tzi||j==tzi)
					cnt--;
				}
			cnt+=x-tzi-1;
			}
		}
ofstream out("nrtri.out");
out<<cnt/3<<"\n";
out.close();
return 0;
}