Cod sursa(job #1022839)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 5 noiembrie 2013 23:39:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<int> v;
int n, a[801], s, nr;

int main()
{
    int x;
    is >> n;
    v.push_back(0);
    for ( int i = 1; i <= n; ++i )
    {
        is >> x;
        v.push_back(x);
    }
    sort( v.begin(), v.end() );
    int p, u;
    int m;
    for ( int i = 1; i <= n; ++i )
            for ( int j = i+1; j <= n; ++j )
            {
                p = j+1;
                u = n;
                while ( p <= u )
                {
                     m = p+(u-p)/2;
                    if ( v[m] <= (v[i]+v[j]) )
                    p = m+1;
                    else
                    u = m-1;
                }
                nr += p-(j+1);
            }

    os << nr;
    return 0;
}