Cod sursa(job #8)

Utilizator fluffyDan-Leonard Crestez fluffy Data 26 noiembrie 2006 23:19:27
Problema Adapost Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#define in "nrtri.in"
#define out "nrtri.out"
#define NMAX 801 
#include <cmath>
using namespace std;

int l[NMAX];//vectorul care retine lungimile segmentelor
int nrsol, n, poz_, suma, dif;

void QSort( int, int);
int BS(int,int);
int Ok( int );

int main()
{
    FILE *fin = fopen( in, "r" );
    FILE *fout = fopen( out, "w" );
    
    fscanf( fin, "%d", &n );
    
    int i, j, k;
    for ( i = 1; i <= n; i++ )
        fscanf( fin, "%d", &l[i] );
    QSort( 1, n );
    
    for ( i = 1; i <= n; i++ )
    {
        for ( j = i + 1; j <= n; j++ )
        {
            suma = l[i] + l[j];
            dif = abs(l[i] - l[j]);
            poz_ = BS( j, n );
            nrsol += abs(poz_ - j);
            
        }
    }
    
    fprintf( fout, "%d\n", nrsol );
    fclose( fin );
    fclose( fout );
    
    return 0;
}

void QSort( int st, int dr )
{
     int pivot = l[st];
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( l[i] < pivot );
         do { j--; } while ( l[j] > pivot );
         if ( i <= j )
         {
              int aux = l[i];
              l[i] = l[j];
              l[j] = aux;
         }
     } while ( i <= j );
     if ( st < j ) QSort( st, j );
     if ( i < dr ) QSort( i, dr );
}

int BS( int st, int dr )
{
     if ( st == dr ) return st;
     if ( st == dr - 1 ) 
     {
          if ( Ok( dr ) ) return dr;
          return st;
     }
     int mij = (st+dr)/2;
     if ( Ok( mij ) ) return BS( mij, dr );
     return BS( st, mij-1);
     
}
 
int Ok( int i )
{
    if ( l[i] <= suma && l[i] >= dif ) return 1;
    return 0;
}