Cod sursa(job #1513043)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 28 octombrie 2015 22:08:30
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <iostream>

using namespace std;

int bin_search(int left,int right,int value ,int a[])
{
    if (left>right) return left-1;

    while (left<right)
    {
        int mid=(left+right+1)/2;

        if (a[mid]<=value) left=mid;
        else right=mid-1;
    }

    if (a[left]>value) return left-1;
    return left;
}

int a[1066];
#include <algorithm>
ifstream f("nrtri.in");
ofstream g("nrtri.out");

int main()
{
    int n,i,j;
    f>>n;
    for(i=1; i<=n; ++i) f>>a[i];
    sort(a+1,a+n+1);

    int result=0;

    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
        {
            int val=a[i]+a[j];
            result+=bin_search(j+1,n,val,a)-j;
        }

    cout<<result<<'\n';

    return 0;
}