Cod sursa(job #204220)

Utilizator IrnukIrina Grosu Irnuk Data 22 august 2008 14:52:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
/*numarare triunghiuri*/

#include<fstream.h>

int id[30001],v[805],n;
long cont;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

void pivotare(int i,int j,int &m)
{

	int pivot=v[i];

	while(i<j)
	{
		while(j>i && v[j]>=pivot) j--;
		v[i]=v[j];
		while(i<j && v[i]<=pivot) i++; 
		v[j]=v[i];
	}
	v[i]=pivot;
	m=i;
}

void quick_sort(int p,int q)
{
	int m;

	if(p<q)
	{
		pivotare(p,q,m); 

		quick_sort(p,m-1);
	
		quick_sort(m+1,q);
	}

}

int cauta(int poz,long s)
{
	poz++;
	while(poz<n)
	{
		if(s>=v[poz])
			poz++;
		else 
			return poz;
	}
	return poz;
	
}

int main()
{
	int i,p,j;
	fin>>n;

	for(i=0;i<n;i++)
	{
		fin>>v[i];
		id[v[i]]=1;
	}
	quick_sort(0,n-1);

	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++)
		{
			p=cauta(j,v[i]+v[j]);
			cont=cont+(p-j-1);
		}


	/*for(i=0;i<n;i++)
	{
		fout<<v[i]<<" ";
	}*/
		fout<<cont<<'\n';
	fout.close();
	return 0;
}