Cod sursa(job #1120781)

Utilizator UgleaEduFMI - Edward UgleaEdu Data 25 februarie 2014 10:06:14
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int Bsearch( int st, int dr, vector <int> v, int c )
{

    int mid = st + ( dr - st ) / 2;

    if ( c > v.back() )

        return  v.size() - 1;

    if ( v[ mid ] == c )

        return mid;

    if ( st < dr )
    {

        if ( v[ mid ] >= c )

            return Bsearch( st, mid - 1, v, c);

        else

            return Bsearch( mid + 1, dr, v, c);

    }
    else

        return mid - 1;

}
int main()
{
    fstream f("nrtri.in");
    int n, i, j, aux, nrT = 0;

    vector<int> v;
    f >> n;


    for ( i = 0; i < n; i++ )
    {

        f >> aux;
        v.push_back( aux );

    }
    f.close();
    sort( v.begin(), v.end() );

    for (  i = 0; i < n - 2; i ++ )

        for ( j = i + 1; j < n - 1; j ++ )
        {

            aux = Bsearch( 0, n - 1, v, v[ i ] + v [ j ] );

            nrT += aux - j;


        }

    ofstream g( "nrtri.out");

    g << nrT;

    g.close();


    return 0;
}