Cod sursa(job #179813)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 16 aprilie 2008 13:08:45
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
int n,v[1100],ls,ld,m,i,j,nr;
int main ()
{
FILE*f=fopen("nrtri.in","r");
FILE*g=fopen("nrtri.out","w");

fscanf(f,"%d",&n);
for (i=1;i<=n;i++) fscanf(f,"%d",&v[i]);

for (i=1;i<=n-1;i++)
    for (j=i+1;j<=n;j++) if (v[i]>v[j]) {m=v[i];
					 v[i]=v[j];
					 v[j]=m;}


for (i=1;i<=n-2;i++)
    for (j=i+1;j<=n-1;j++)
       {
	ls=j+1;
	ld=n;
	m=(ls+ld)/2;
	while (ls<=ld)
	{
      if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n))
		  {nr=nr+m-j;break;}
	  else if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j]) {
		  ls=m+1;
		  m=(ls+ld)/2;
	  }
	  else {
		  ld=m-1;
		  m=(ls+ld)/2;
		  }
	}
       }
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;

}