Pagini recente » Cod sursa (job #209886) | Cod sursa (job #2245227) | Cod sursa (job #926283) | Cod sursa (job #2707011) | Cod sursa (job #2705556)
#include <bits/stdc++.h>
#define N 808
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n;
int v[N];
void Citire()
{
int i;
fin >> n;
for( i=1; i<=n; i++ )
fin >> v[i];
}
int CautareBinara( int i, int j )
{
int st, dr;
int mij;
int poz = -1;
st = 1; dr = n;
while( st <= dr )
{
mij = ( st + dr ) / 2;
if( v[mij] <= v[i] + v[j] )
{
st = mij + 1;
poz = mij;
}
else if( v[mij] > v[i] + v[j] )
{
dr = mij - 1;
}
}
return poz;
}
inline bool triunghi( int a, int b, int c )
{
if( a + b < c ) return 0;
if( a + c < b ) return 0;
if( c + b < a ) return 0;
return 1;
}
void Rezolvare()
{
int i, j;
int x;
int cb;
int ct = 0;
sort( v+1, v+n+1 );
for( i=1; i<n; i++ )
for( j=i+1; j<=n; j++ )
{
x = v[i] + v[j];
cb = CautareBinara( i, j );
//cout << i << " " << j << ": " << cb << " " << triunghi( v[i], v[j], v[cb] ) << "\n";
if( triunghi( v[i], v[j], v[cb] ) ) ct += ( cb - j );
}
fout << ct;
}
int main()
{
Citire();
Rezolvare();
fin.close();
fout.close();
return 0;
}