Cod sursa(job #896159)

Utilizator alexarnautuArnautu Alexandru alexarnautu Data 27 februarie 2013 14:08:08
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> l;
int n, i, j, k, x, sol;
int binary_s(int key)
{
    int right=0, left=n-1, mid;

    mid = (right+left)/2;

    while(right < left)
    {
        mid = (right+left)/2;
        if(l[mid] <= key)
            right = mid + 1;
        else
            left = mid;
    }
    mid = (right+left)/2;
    if(l[mid] > key)
        --mid;
    mid = n-1-mid;
    return mid;
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    scanf("%d", &n);

    for(i=1;i<=n;i++)
        scanf("%d", &x), l.push_back(x);

    stable_sort(l.begin(), l.end());

    for(i=0;i<n-2;i++)
    {
        for(j=i+1;j<n-1;j++)
        {
            sol+=binary_s(l[i]+l[j]);
        }
    }


    printf("%d", sol);

    return 0;
}