Cod sursa(job #325718)

Utilizator iulia609fara nume iulia609 Data 22 iunie 2009 00:02:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>   
#define dim 801   
using namespace std;   
  
int n, a[dim],in,sf;   
  
void qsort(int in,int sf)   
    {int i,j;   
     int temp,aux;   
     i=in,j=sf;   
     temp=a[(i+j)>>1];   
        
     do  
       {while(a[i]<temp)i++;   
        while(a[j]>temp)j--;   
        if(i<j) aux=a[i],a[i]=a[j],a[j]=aux;   
        if(i<=j)j--,i++;   
        } while(i<=j);   
     if(in<j)qsort(in,j);   
     if(i<sf)qsort(i,sf);   
     }   
	
int cb(int in, int sf)
{
  int m,i,j;
  m=(in + sf) / 2;
  while (in <= sf)
	  {
       if ((a[m] <= a[i] + a[j] && a[m+1] > a[i] + a[j]) || (a[m] <= a[i] + a[j] && m == n))
		  return m;
	   else if (a[m] <= a[i] + a[j] && a[m+1] <= a[i] + a[j]) {
		  in = m + 1; 
		  m =(in + sf) / 2;
	  }
	  else {
		  sf = m - 1; 
		  m = (in + sf) / 2;
		  }  
  }
  return 0;
}

int main()
{ int i,j,k,cont = 0;
	
	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", &a[i]);
	
	qsort(1,n);
	
	for(i = 1; i <= n-2; i++)
		for(j = i+1; j <= n-1; j++)
			cont += (cb(1,n) - j) ;
				
	fprintf(g,"%d\n", cont);	
	
	fclose(f);
	fclose(g);
	return 0;
}