Cod sursa(job #1026717)

Utilizator tatianazTatiana Zapirtan tatianaz Data 11 noiembrie 2013 21:48:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int n;
int a[801];
int dr, st, m, cnt;

int main()
{
    is >> n;
    for ( int i = 1; i <= n; i++ )
        is >> a[i];

    sort(a, a + n + 1);

    for ( int i = 1; i <= n - 2; ++i )
        for ( int j = i + 1; j <= n - 1; ++j )
        {
            st = j + 1;
            dr = n;
            while ( st <= dr )
            {
                m = (st + dr)/2;
                if ( a[m] <= a[i] + a[j] )
                    st = m + 1;
                else
                    dr = m - 1;

            }
            cnt += st - j - 1;
        }

    os << cnt;

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