Pagini recente » Cod sursa (job #2268544) | Cod sursa (job #2103281) | ojitime | Cod sursa (job #518848) | Cod sursa (job #8)
Cod sursa(job #8)
#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;
}