Cod sursa(job #546950)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 5 martie 2011 17:59:13
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream.h>
ifstream f("ntri.in");
ofstream g("ntri.out");
int n,v[100005],vs[500005],nn=0,general=0,k;

void vectordesume()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)		
		{
			vs[++nn]=v[i]+v[j];
			if(j<n)
			{
				k=j+1;
				while(k<=n)			
					if(v[k++]<=vs[nn]) general++;
			}
		}
}

void sorteaza(int st,int dr)
{
	int temp,min,max,mij;
	mij=v[st+(dr-st)/2];
	min=st;
	max=dr;
	while(min<=max)
	{
		while(v[min]<mij) min++;
		while(v[max]>mij) max--;
		if(min<=max)
		{
			temp=v[min];
			v[min++]=v[max];
			v[max--]=temp;
		}
	}
	if(st<max) sorteaza(st,max);
	if(dr>min) sorteaza(min,dr);
}

int main()
{
	int i;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	sorteaza(1,n);	
	vectordesume();				
	g<<general<<'\n';
	f.close();
	g.close();
	return 0;
}