Cod sursa(job #205826)
#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 (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;
}