Cod sursa(job #2795423)

Utilizator CristiBota3Cristian Bota Avram CristiBota3 Data 6 noiembrie 2021 12:29:09
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
using namespace std;


int cautarebinara(int v[],int val,int start,int stop)
{
    if(start>=stop)
    {
        return start;
    }
    int mij;
    mij=(start+stop)/2;
    if(v[mij-1]<=val && v[mij]>val)
    {
       return mij-1;
    }
    else if(v[mij]<val)
    {
        start=mij;
    }
    else
    {
        stop=mij;
    }
    return cautarebinara(v,val,start,stop);
}

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


    int n,v[801],nrt=0;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    sort(v+1,v+n);
    for(int i=1;i<=n-2;i++)
    {
        int b1=v[i];
        for(int j=i+1;j<=n-1;j++)
        {
            int b2=v[j];
            int b3=cautarebinara(v,b1+b2,j+1,n);
            if(b1+b2>v[b3])
            nrt+=b3-j;



//            for(int g=j+1;g<=n;g++)
//            {
//
//                int b3=v[g];
//                if(b1+b2>=b3 && b2+b3>=b1 && b3+b1>=b2)
//                {
//                    nrt++;
//                }
//            }
        }
    }
    fout<<nrt;
    fin.close();
    fout.close();
    return 0;
}