Cod sursa(job #2093229)

Utilizator iDanyelArvat Ovidiu Daniel iDanyel Data 23 decembrie 2017 11:30:39
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

int binary(int a, int b, int n, int v[])
{
    int li=b+1, lf=n, poz=0;

    while(li<=lf)
    {
        int mid=(li+lf)/2;

        if((v[mid]<=v[a]+v[b])&&(v[a]<=v[b]+v[mid])&&(v[b]<=v[a]+v[mid]))
            poz=mid, li=mid+1;
        else
            lf=mid-1;
    }

    return poz;
}

int main()
{
    int n, v[1000], no=0;
    fin >> n;

    for(int i=1;i<=n;i++)
        fin >> v[i];

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

    for(int i=1;i<=n-2;i++)
        for(int j=i+1;j<=n-1;j++)
            if(binary(i,j,n,v))
                no+=binary(i,j,n,v)-j;

    fout << no;
    return 0;
}