Cod sursa(job #205827)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 3 septembrie 2008 00:09:31
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 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;
scanf("%d",&N);
for (int i=1;i<=N;++i)
scanf("%d", A+i);
q_sort(A,1,N);
int nr=0;
for (int i=1;i<=N-2;++i)
for (int j=i+1;j<=N-1;++j)
for (int 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;
}