Cod sursa(job #2685381)

Utilizator Anna123Anna Negrea Anna123 Data 16 decembrie 2020 19:01:02
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
#define DimMax 800

using namespace std;

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

short n;
short v[DimMax];
int ans;

int CautaBinar ( int sum, int pos )
{
    int sol = -1;
    int st = pos; int dr = n - 1;
    while ( st <= dr )
    {
        int mij = (st + dr) / 2;
        if ( v[mij] > sum )
        {
            sol = mij;
            dr = mij - 1;
        } else st = mij + 1;
    }

    if ( sol == -1 )
        return 0;
    return (n - sol);
}


int main()
{
    fin >> n;
    for ( int i = 0; i < n; i++ )
        fin >> v[i];

    sort(v, v + n);

    for ( int i = 0; i < n - 2; i++ )
        for ( int j = i + 1; j < n - 1; j++ )
        {
            int sum = v[i] + v[j];
            ans += CautaBinar( sum, j + 1);
        }

    fout << ans;
    return 0;
}