Cod sursa(job #2154285)

Utilizator HumikoPostu Alexandru Humiko Data 6 martie 2018 20:37:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
#define nmax 805

using namespace std;

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

int n, interval, ans, v[nmax];

int binara (int val, int st, int dr)
{
    if ( st > dr )
        return dr;
    int mij = st+(dr-st)/2;
    if ( val >= v[mij] )
        binara (val, mij+1, dr);
    else
        binara (val, st, mij-1);
}

int main()
{
    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 )
        {
            interval = binara(v[i]+v[j], 1, n);
                if ( interval )
                    ans += interval-j;
        }
    fout<<ans<<'\n';
}