Cod sursa(job #361341)

Utilizator mirunababliucMiruna Babliuc mirunababliuc Data 4 noiembrie 2009 18:50:09
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda CNRV #4 Marime 0.6 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int main ()
{ int v[800],i,nr=0,st,dr,j,m,n,ok;
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]);
sort(v+1, v+1+n);
for(i=1; i<=n-2; i++)
	for(j=i+1; j<=n-1; j++)
		{ st=j+1;
	      dr=n;
		  ok=1;
		  while (st<=dr && ok)
			  { m=(st+dr)/2;
				if (v[m]<=v[i]+v[j] && (v[m+1]>v[i]+v[j]|| m+1==n)) { nr+=m-j; ok=0;}
		        else if (v[m]>v[i]+v[i]) dr=m-1;
			         else st=m+1;
			  }
		}
fprintf(g,"%d",nr);
fclose (f);
fclose (g);
return 0;
}