Cod sursa(job #227360)

Utilizator Andrei200Andrei200 Andrei200 Data 4 decembrie 2008 10:40:31
Problema Numarare triunghiuri Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>   
#include <stdlib.h>   
     
int A[800];   
  
void q_sort(int numbers[], int left, int right)   
{   
   int pivot, l_hold, r_hold;   
   l_hold = left;   
   r_hold = right;   
   if(left != right)   
   {   
    int aux = numbers[left], randompoz = left + rand() % (left - right);   
    numbers[left] = numbers[randompoz];   
    numbers[randompoz] = aux;   
   }   
   pivot = numbers[left];   
   while (left < right)   
   {   
      while ((numbers[right] >= pivot) && (left < right))   
      right--;   
      if (left != right)   
      {   
    numbers[left] = numbers[right];   
    left++;   
      }   
      while ((numbers[left] <= pivot) && (left < right))   
    left++;   
      if (left != right)   
      {   
      numbers[right] = numbers[left];   
      right--;   
      }   
   }   
   numbers[left] = pivot;   
   pivot = left;   
   left = l_hold;   
   right = r_hold;   
   if (left < pivot)   
      q_sort(numbers, left, pivot-1);   
   if (right > pivot)   
      q_sort(numbers, pivot+1, right);   
}   
  
  
int main()      
{   
freopen("nrtri.in","rt",stdin);   
int N,i;   
scanf("%d",&N);   
for ( i=1;i<=N;++i)   
     scanf("%d", A+i);
q_sort(A,1,N);   
int nr=0,j,k;   
for (i=1;i<=N-2;++i)   
for (j=i+1;j<=N-1;++j)   
for (k=j+1;k<=N;++k)   
if (A[k]<=A[i]+A[j] && A[j]<=A[k]+A[i] && A[i]<=A[k]+A[j]) nr++;      
freopen("nrtri.out","wt",stdout);   
printf("%d\n",nr);   
return 0;   
}