Cod sursa(job #281846)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 16 martie 2009 07:53:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream.h>
ifstream in("nrtri.in");
ofstream out("nrtri.out");
long x[1000],i,j,n,s,k;
int bin(int a, int b, int st, int dr)
{
int mij=(st+dr)/2;
if(x[mij]<=a+b && x[mij]>=a-b)
	return mij;
if(st==dr)
	return 0;
else
	{
	int k1=bin(a,b, st, mij);
	int k2=bin(a,b, mij+1, dr);
	return k1+k2;
	}
}

void sort(int k)
{
int t;
while(x[k]<x[k-1]&&n>1)
	{
	t=x[k];
	x[k]=x[k-1];
	x[k-1]=t;
	k--;
	}
}

int main()
{
in>>n;
for(i=1; i<=n; i++)
	{in>>x[i];sort(i);}
for(i=1; i<n-1; i++)
	for(j=i+1; j<n; j++)
		{
		k=bin(x[i],x[j],j+1,n);
		if(k)
			s+=(k-j);
		}
out<<s;
return 0;
}