Cod sursa(job #268314)

Utilizator conttPop Mircea contt Data 1 martie 2009 01:26:37
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream.h>
#include <iostream.h>
int cnt=0,st[1000],a[1000],n;

int afisare()
{
     if  (a[st[1]]+a[st[2]]>=a[st[3]])
    { cnt++;return 1;}
    return 0;
     }
    
    
void back(int p)
{
      int pval;
      for(pval=st[p-1]+1;pval<=n;pval++)
         {st[p]=pval;
         
           if (p==3) { if (!afisare()) break;}
           else back(p+1);
           
           }
           }
     
    
    
/*  Swap:  Swap two item (by reference).
 */

void  Swap( int &v1, int &v2 )
{
    int  tmpVal;

    tmpVal = v1;
    v1 = v2;
    v2 = tmpVal;
}

    /*  Pivot:  Find and return the index of pivot element.
 */

int Pivot( int a[1000], int first, int last ) 
{
    int  p = first;
    int pivot = a[first];

    for( int i = first+1 ; i <= last ; i++ ) {
        if( a[i] <= pivot ) {
            p++;
            Swap( a[i], a[p] );
        }
    }

    Swap( a[p], a[first] );

    return p;
}


           
void Quicksort( int a[1000], int first, int last ) 
{
    int piv;

    if( first < last ) {
        piv = Pivot( a, first, last );
        Quicksort( a, first, piv-1 );
        Quicksort( a, piv+1, last );
    }
}


int fa()
{
    int k=0,i,j,z,suma;
    for(i=1;i<=n-2;i++)
      for(j=i+1;j<=n-1;j++)
        
        {suma=a[i]+a[j];
         z=j;
          while (suma<=a[z+1]&&z+1<=n) z++;
          k=k+z-j;
          }
        return k;
          }
         

int main()
{int i;
    ifstream f("nrtri.in");
    f>>n;
    for(i=1;i<=n;i++)
    f>>a[i];
    f.close();
    Quicksort(a,1,n);
    //back(1);
    cnt=fa();
    ofstream g("nrtri.out");
    g<<cnt;
    g.close();
}