Pagini recente » Cod sursa (job #1775432) | Cod sursa (job #2488706) | Cod sursa (job #621817) | Cod sursa (job #1801432) | Cod sursa (job #2065688)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[801];
int part_Hoare ( int s, int d )
{
int i, j;
i = s-1;
j= d+1;
int randpoz, r1, r2, r3;
int nr = d-s+1;
r1 = rand() % nr + s;
r2 = rand() % nr + s;
r3 = rand() % nr + s;
int minr, maxr;
minr = min ( min(r1, r2), min(r2, r3) );
maxr = max ( max(r1, r2), max(r2, r3) );
randpoz = r1+r2+r3 - minr-maxr;
int pivot = v[randpoz];
while (true){
do
{
++i;
}while( v[i] < pivot);
do
{
--j;
}while( v[j] > pivot);
if( i>=j )
return j;
swap(v[i], v[j]);
}
}
void qsort (int i, int j)
{
if(i<j){
int k = part_Hoare( i, j );
qsort(i, k);
qsort(k+1, j);
}
}
int caut_bin (int st, int dr, int x)
{
int m = ( st + dr ) / 2;
if( st >= dr )
{
if( v[m] <= x )
return dr;
else
return st-1;
}
if( x < v[m] )
return caut_bin( st, m-1, x );
else
//if( x >= v[m] )
return caut_bin( m+1, dr, x );
}
int main()
{
int n, i;
fin>>n;
for(i=1; i<=n; i++)
fin>>v[i];
qsort(1, n);
int j, ind, k=0;
for(i=1; i<= n-2; i++){
for(j=i+1; j<=n-1; j++)
{
ind = caut_bin( j + 1, n, v[i]+v[j] );
if( (v[i] +v[j]) >= v[ind] )
k += (ind - j);
}
}
fout<<k;
}