Cod sursa(job #2743115)

Utilizator LORDENVraja Luca LORDEN Data 22 aprilie 2021 16:20:13
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n, S, p ;
vector < int > v ;

int main()
{

    int x, st, dr, mij, triunghiuri = 0 ;

    cin >> n ;

    for (int i = 1 ; i <= n ; i ++)
        cin >> x, v.push_back(x) ;

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

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

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

            S = v [i] + v [j] ;
            p = -1 ;
            st = j + 1 ;
            dr = n ;
            mij = ( st + dr ) / 2 ;

            while ( st <= dr )
            {
                if ( v [ mij ] == S )
                {
                    p = mij ;
                    st ++ ;
                }
                else if ( v [ mij ] < S )
                {
                    st = mij + 1 ;
                }
                else
                {
                    dr = mij - 1 ;
                }
                mij = ( st + dr ) / 2 ;
            }

            if ( p == -1 )
                p = dr ;

            triunghiuri = triunghiuri + p - j ;

        }
    }

    cout << triunghiuri ;

    return 0 ;

}