Cod sursa(job #2146212)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 27 februarie 2018 21:09:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, sol;
int arr[805];

int cautBinar( int st, int dr, int val )
{
    if( st > dr )
    {
        return dr;
    }

    int mid = (st + dr)/2;

    if( arr[mid] <= val )
        return cautBinar( mid + 1, dr, val );
    else
        return cautBinar( st, mid - 1, val );
}

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

    sort( arr + 1, arr + 1 + n );

    for( int i = 1; i <= n - 1; i++ )
        for( int j = i + 1; j <= n; j++ )
            sol += cautBinar( j + 1, n, arr[i] + arr[j] ) - j;

    out<<sol;

    return 0;
}