Cod sursa(job #2231884)

Utilizator anne_marieMessner Anne anne_marie Data 16 august 2018 13:57:10
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream >
#include <algorithm>

using namespace std;

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

int v[803],n;

cautbin(int x)
{
    int stanga = 1, dreapta = n, rasp = -1, mijloc;
    while( stanga <= dreapta )
    {
        mijloc = ( stanga + dreapta ) / 2;
        if( v[mijloc] <= x)
        {
            stanga = mijloc + 1;
            rasp = mijloc;
        }
        else
        {
            dreapta = mijloc - 1;
        }
    }
    return rasp;
}

int main()
{
    int x, k, nr = 0;
    fin >> n;
    for( int i = 1 ; i <= n ; i++)
        fin >> v[i];
    sort(v+1, v+n+1);
    for( int i = 1 ; i <= n - 1 ; i++)
        for( int j = i + 1 ; j <= n; j++)
        {
            x = v[i] + v[j];
            k = cautbin(x);
            nr = nr + ( k - j );
        }
        fout << nr << '\n';
        return 0;
}