Cod sursa(job #1684300)

Utilizator Mr.RobotElliot Alderson Mr.Robot Data 10 aprilie 2016 22:36:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int n, v[1000], i, j, nr;

int cbin( int st, int dr )
{
    if( st == dr )
        return st;
    else
    {
        int mij = st + (dr - st)/2;

        if( v[mij] <= v[i] + v[j] )
            return cbin( mij + 1, dr );
        else
            return cbin( st, mij );
    }
}

int main()
{
    in >> n;

    for(  i = 1; i <= n; i ++ )
        in >> v[i];

    sort( v + 1, v + n + 1 );

    for( i = 1; i <= n - 2; i ++ )
        for( j = i + 1; j <= n - 1; j ++ )
        {
            int p;
            p = cbin( j + 1, n );
            if( v[p] > v[i] + v[j] )
            {
                while( p > j && v[p] > v[i] + v[j] )
                    p--;
            }
            else
            {
                while( p < n && v[p+1] <= v[i] + v[j] )
                    p++;
            }
            nr += p - j;
        }

    out << nr;

    return 0;
}