Cod sursa(job #209330)

Utilizator tamicTamas Iulia tamic Data 21 septembrie 2008 20:42:15
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>

FILE *fin,*fout;
long a[1001];
long i,j,n;
long rez,total=0,m;

int caut(long l, long r){
	long m;
   m=(l+r)/2;
   while(l<=r){
   	if((a[i]+a[j]>=a[m] && a[i]+a[j]<a[m+1]) || (a[i]+a[j]>=a[m] && m==n))
      	return m;
      else if(a[i]+a[j]>=a[m] && a[i]+a[j]>=a[m+1]){
      	l=m+1; m=(l+r)/2; }
      else{ r=m-1; m=(l+r)/2; }
   }
   return 0;
}

void sort(long l,long r){
	long i,j,x,y;
   i=l; j=r; x=a[(l+r)/2];
   do{
   	while(a[i]<x) i++;
      while(x<a[j]) j--;
      if(i<=j){
      	y=a[i]; a[i]=a[j]; a[j]=y;
         i++; j--;
      }
   }while(i<=j);
   if(l<j) sort(l,j);
   if(i<r) sort(i,r);
}

int main(){
	fin=fopen("nrtri.in","r");
   fout=fopen("nrtri.out","w");
   fscanf(fin,"%ld",&n);
   for(i=1;i<=n;i++) fscanf(fin,"%ld",&a[i]);
   sort(1,n);
   for(i=1;i<=n-1;i++)
   	for(j=i+1;j<=n;j++){
      	m=caut(1,n);
         total += m-j;
      }
   fprintf(fout,"%ld\n",total);
   fclose(fin); fclose(fout);
   return 0;
}