Cod sursa(job #63890)

Utilizator znakeuJurba Andrei znakeu Data 31 mai 2007 12:48:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>

int v[805],n;

int comp(const void *a, const void *b)
{
	int *aa=(int*) a, *bb=(int*) b;
	int x=*aa, y=*bb;
	if (x<y)
		return -1;
	if (x>y)
		return 1;
	return 0;
}


int main()
{
	int nrtri=0,i,j,kl,kr,x;
	
	FILE *in=fopen("nrtri.in","r");
	
	fscanf(in,"%d",&n);
	for (i=0; i<n; i++)
		fscanf(in,"%d",&v[i]);
	fclose(in);
	qsort(v,n,sizeof(v[0]),comp);
	
	for (i=0; i<n-2; i++)
		for (j=i+1; j<n-1; j++)
		{
			kl=j+1;
			kr=n-1;
			while (!((v[i]+v[j]>=v[kl])&&(v[j]+v[kl]>=v[i])&&(v[i]+v[kl]>=v[j])) && kl+10<n)
				kl+=10;
			while (!((v[i]+v[j]>=v[kl])&&(v[j]+v[kl]>=v[i])&&(v[i]+v[kl]>=v[j])) && kl<n)
				kl++;
			while (!((v[i]+v[j]>=v[kl])&&(v[j]+v[kl]>=v[i])&&(v[i]+v[kl]>=v[j])) && kl>j)
				kl--;
			
			while (!((v[i]+v[j]>=v[kr])&&(v[j]+v[kr]>=v[i])&&(v[i]+v[kr]>=v[j])) && kr-10>j)
				kr-=10;
			while (!((v[i]+v[j]>=v[kr])&&(v[j]+v[kr]>=v[i])&&(v[i]+v[kr]>=v[j])) && kr>j)
				kr--;
			while (!((v[i]+v[j]>=v[kr])&&(v[j]+v[kr]>=v[i])&&(v[i]+v[kr]>=v[j])) && kr<n)
				kr++;
			if (kr>=kl)
				nrtri+=kr-kl+1;
		}
	
	
	FILE *out=fopen("nrtri.out","w");
	fprintf(out,"%d\n",nrtri);
	fclose(out);
	
	return 0;
}