Cod sursa(job #44878)

Utilizator DastasIonescu Vlad Dastas Data 31 martie 2007 19:32:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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];
            int x = j+1;
            int y = n-1;
            int c = x;
            int tmpcnt = 0;

            // 2 3 4 7

            // 1 2 3 4 5 6 7 8 9 10

            while ( x <= y )
            {
                int m = (x+y)/2;
                if ( a[m] <= s )
                {
                    //s = a[m];
                    x = m+1;
                    //c = m;
                    tmpcnt = m-j;
                }
                else
                {
                    y = m-1;
                }
            }
            cnt += tmpcnt;
            //cout << cnt << endl;
        }
    }

    out << cnt << endl;

    return 0;
}