Cod sursa(job #1026702)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 11 noiembrie 2013 21:40:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream is ("nrtri.in");
ofstream os ("nrtri.out");

int n;
vector<int> v;
int nrt;
int s;

int Verif( int st );

int main()
{
    is >> n;
    v.push_back(0);
    int x;
    for ( int i = 1; i <= n; ++i )
    {
        is >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    for ( int i = 1; i <= n - 2; ++i )
        for ( int j = i + 1; j <= n - 1; ++j )
        {
            s = v[i] + v[j];
            nrt += Verif(j) - j - 1;
        }
    os << nrt;

    is.close();
    os.close();
    return 0;
}

int Verif( int st )
{
    int m, dr;
    dr = n;
    while ( st < dr )
    {
        m = (st + dr) / 2;
        if( v[m] > s )
            dr = m - 1;
        else
            st = m + 1;
    }
    if( s >= v[dr] )
        ++dr;
    return dr;
}