Cod sursa(job #227363)

Utilizator Andrei200Andrei200 Andrei200 Data 4 decembrie 2008 10:45:22
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>      
#include <stdlib.h>      
        
int A[800],n;      
     
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 cautare(int p, int u)
{
  int m,i,j;
  m=(p+u)/2;
  while (p<=u)
  {
      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]) 
      {
		  p=m+1; 
		  m=(p+u)/2;
	  }
	  else 
      {
	  u=m-1; 
	  m=(p+u)/2;
	  }  
  }
  return 0;
}
     
     
int main()         
{      
freopen("nrtri.in","r",stdin);      
freopen("nrtri.out","w",stdout);
int 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-1;++i)
    //for (j=1;j<n;++j)
  //  {
    nr+=cautare(i,n));
    //}
//freopen("nrtri.out","wt",stdout);      
printf("%d\n",nr);      
return 0;      
}