Cod sursa(job #44776)

Utilizator DastasIonescu Vlad Dastas Data 31 martie 2007 18:40:20
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int a[800];
int cnt = 0;

int qspart(int s, int d)
{
    int x = a[s];

    while ( s < d )
    {
        while ( a[d] >= x && s < d )
            --d;
        a[s] = a[d];
        while ( a[s] <= x && s < d )
            ++s;
        a[d] = a[s];
    }

    a[s] = x;
    return s;
}

void qs(int s, int d)
{
    int m = qspart(s, d);

    if ( s < m )
        qs(s, m-1);
    if ( m < d )
        qs(m+1, d);
}

void read()
{
    in >> n;
    for ( int i = 0; i < n; ++i )
        in >> a[i];

    qs(0, n-1);
}

int main()
{
    read();

    for ( int i = 0; i != n; ++i )
    {
        for ( int j = i+1; j != n; ++j )
        {
            int s = a[i]+a[j];
            for ( int k = j+1; k != n; ++k )
                if ( s >= a[k] )
                    ++cnt;
        }
    }

    out << cnt << endl;

    return 0;
}