Cod sursa(job #361904)

Utilizator Cristi09Cristi Cristi09 Data 7 noiembrie 2009 08:54:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda CNRV #4 Marime 0.78 kb
#include<stdio.h>
//#include<conio.h>
//#include<iostream.h>
#include<stdlib.h>
int fcmp(const void* a,const void* b)
{
	return *(int*)a-*(int*)b;
}
int main()
{  //clrscr();
   int n,i;
   long v[800],sol=0,var;

   FILE *f=fopen("nrtri.in","r");

   fscanf(f,"%d",&n);

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

   fclose(f);

   qsort(v,n,sizeof(long),fcmp);

   int k=0,j,ok,a,b,c;
   for(k;k<n-2;++k)
   {
	  for(i=k+1;i<n-1;++i)
	  {
		  var=v[i]+v[k];
		  a=i;
		  b=n-1;
		  c=((a+b)/2);
		  while(v[c]<=var&&a!=b)
		  {
			 a=c+1;
			 c=(a+b)/2;
		  }
		  ok=1;
		  for(j=c;j>=i+1&&ok;--j)
		  if(v[j]<=var)ok=0;

		  if(!ok)sol+=(j+1)-i;

	   }
   }
   FILE*g=fopen("nrtri.out","w");
   fprintf(g,"%d",sol);
   fclose(g);
   return 0;
}