Cod sursa(job #1126037)

Utilizator UgleaEduFMI - Edward UgleaEdu Data 26 februarie 2014 20:52:31
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

int Bsearch( int st, int dr, vector<int> v, int c)
{

    if ( c > v.back() )

        return n - 1;

    while ( st <= dr )
    {

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

        if ( v [ mid ]  == c )
        {
            while ( v[ mid + 1 ] == v[ mid ] )

                mid ++;

            return mid;
        }

        if ( v[ mid ] > c )

            dr = mid - 1;
        else

            st = mid + 1;

    }


    return st - 1;

}



int main()
{

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

    int i, aux, j, nrtri = 0;

    vector <int> v;

    f >> n;

    v.resize( n + 1);

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

        f >> aux;
        v[i] =  aux;

    }


    sort( v.begin(), v.end() );



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

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

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

            nrtri +=  ( aux - j );


        }
    g << nrtri;


    return 0;
}