Cod sursa(job #360952)

Utilizator petroMilut Petronela petro Data 2 noiembrie 2009 22:55:29
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda CNRV #4 Marime 0.83 kb
#include<stdio.h>
FILE *f=fopen("nrtri.in","r");
FILE *g=fopen("nrtri.out","w");

int v[802],n;

void cit()
{
	int i;
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	fclose(f);
}

int poz(int i, int j)
{
	int p,q,x;
	p=i;
	q=j;
	x=v[i];
	
	while(p<q)
	{
		while(p<q && x<=v[q])
			q--;
		v[p]=v[q];
		
		while(p<q && x>v[p])
			p++;
		v[q]=v[p];
	}
	
	v[p]=x;
	return p;
}

void quick(int i,int j)
{
	if(i<j) {int m=poz(i,j);
	         if(i<m-1) quick(i,m-1);
	         if(j>m+1) quick(m+1,j);
	         }
}

void rez()
{
	int i,j,k;
	long nr=0;
	
	for(i=1;i<=n-2;i++)
		for(j=i+1;j<=n-1;j++)
			for(k=j+1;k<=n;k++)
				if(v[i]+v[j]<=v[k]) nr++;
			    else break;

    fprintf(g,"%ld\n",nr);
	fclose(g);
}				

int main()
{
	cit();
	quick(1,n);
	rez();
	return 0;
}