Cod sursa(job #2743088)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 22 aprilie 2021 15:49:50
Problema Numarare triunghiuri Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>

#include <algorithm>

using namespace std;

ifstream in ( "nrtri.in" ) ;

ofstream out ( "nrtri.out" ) ;

int n, i1, i2, i3, v [ 801 ], k, a, b, c, st, dr, p, mij, i, j, S ;

bool triunghi ( int a, int b, int c )
{
    if ( v [ i1 ] + v [ i2 ] >= v [ i3 ] && v [ i3 ] + v [ i2 ] >= v [ i1 ] && v [ i1 ] + v [ i3 ] >= v [ i2 ] )
        return true ;
    else return false ;
}
int main()
{
    in >> n ;
    /*for ( i1 = 1 ; i1 <= n ; i1 ++ )
    {
        in >> v [ i1 ] ;
    }
    for ( i1 = 1 ; i1 <= n - 2 ; i1 ++ )
    {
        for ( i2 = i1 + 1 ; i2 <= n - 1 ; i2 ++ )
        {
            for ( i3 = i2 + 1 ; i3 <= n ; i3 ++ )
            {
                if ( triunghi ( v [ i1 ] , v [ i2 ] , v [ i3 ] ) )
                    k ++ ;
            }
        }
    }*/
    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 ; 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 ;
                        break ;
                    }
                else if ( v [ mij ] < S )
                {
                    st = mij + 1 ;
                }
                else
                {
                    dr = mij - 1 ;
                }
                mij = ( st + dr ) / 2 ;
            }
            if ( p == -1 )
                p = dr ;
            k = k + p - j ;
        }
    }
    out << k ;
    return 0;
}