Cod sursa(job #63906)

Utilizator znakeuJurba Andrei znakeu Data 31 mai 2007 14:08:12
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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=0,kr=0,l,r;
	
	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++)
		{
			l=j+1; r=n-1; kl=(l+r)/2;
			while (kl!=l && kl!=r) 
			{
				if ((v[i]+v[j]>=v[kl])&&(v[j]+v[kl]>=v[i])&&(v[i]+v[kl]>=v[j]))
					r=kl;
				else
					if (v[i]+v[j]>=v[kl])
						l=kl;
					else
						r=kl;
				kl=(l+r)/2;
			}
			if ((v[i]+v[j]>=v[kl-1])&&(v[j]+v[kl-1]>=v[i])&&(v[i]+v[kl-1]>=v[j]))
				kl--;
			
			l=j+1; r=n-1; kr=(l+r)/2;
			while (kr!=l && kr!=r) 
			{
				if ((v[i]+v[j]>=v[kr])&&(v[j]+v[kr]>=v[i])&&(v[i]+v[kr]>=v[j]))
					l=kr;
				else
					if (v[i]+v[j]>=v[kl])
						r=kr;
					else
						l=kr;
				kr=(l+r)/2;
			}
			if ((v[i]+v[j]>=v[kr+1])&&(v[j]+v[kr+1]>=v[i])&&(v[i]+v[kr+1]>=v[j]))
				kr++;
			if (kr>=kl)
				nrtri+=kr-kl+1;
		}
	
	
	FILE *out=fopen("nrtri.out","w");
	fprintf(out,"%d\n",nrtri);
	fclose(out);
	
	return 0;
}