Cod sursa(job #325717)

Utilizator iulia609fara nume iulia609 Data 22 iunie 2009 00:01:01
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>   
#define dim 801   
using namespace std;   
  
int n, v[dim],b[dim],in,sf;   
  
void mergesort(int i, int m, int j)   
{int x=i,k=1,y=m+1;   
 while((x<=m)&&(y<=j))   
     if(v[x]<v[y])   
     {b[k++]=v[x++];}   
      else  
          b[k++]=v[y++];   
 while(x<=m)   
   {b[k++]=v[x++];}   
 while(y<=j)   
   {b[k++]=v[y++];}   
 int t=i;   
 for(k=1;k<=(j-i)+1;k++)   
     {v[t++]=b[k];}   
}   
  
  
void divimp(int i, int j)   
{if(i<j)   
  {int m=(i+j)>>1;   
   divimp(i,m);   
  divimp(m+1,j);   
   mergesort(i,m,j);   
   }       
}   


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", &v[i]);
	
	divimp(1,n);
	
	for(i = 1; i <= n-2; i++)
		for(j = i+1; j <= n-1; j++)
			for(k = j+1; k <= n; k++)   
                if(v[i] + v[j] >= v[k]) cont++;
					else break;
				
	fprintf(g,"%d\n", cont);	
	
	fclose(f);
	fclose(g);
	return 0;
}