Cod sursa(job #3153853)

Utilizator deliaandreeaddelia andreea deliaandreead Data 1 octombrie 2023 17:03:29
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <algorithm>

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

int v[805],rezc[805];
int cont=0,n,a,b,c;

 void cautbin2(){
    for(int j=1;j<=c;j++){// j reprez val pe care le poate lua c
        int st2=1;
        int dr2=n;
        while(st2<=dr2){
            int mij=(st2+dr2)/2;
            if(j>v[mij]){
                st2=mij+1;
            }
            else if(j<v[mij]){
                dr2=mij-1;
            }
            else if(v[mij]==j){
                cont++;
            }
        }
    }
}

bool verif(int c){// abc tri daca sum a 2 l > a 3a l
   if(v[a]+v[b]>=v[c] && v[b]+v[c]>=v[a] && v[a]+v[c]>=v[b]){
        if(c!=a && c!=b){
            //cout<<v[a]<<" "<<v[b]<<" "<<v[c]<<endl;
            return true;
        }
        else{
            return false;
        }
   }
   else{
        return false;
   }
}

void cautbin(){
    int st=1;
    int dr=n;
    while(st<=dr){
         c=(st+dr)/2;
        if(verif(c)){
            dr=c-1;
        }
        else{
            st=c+1;
        }
    }// v[c] e cea mai mare val pe care poate sa o ia
    cautbin2();// caut cate val pe care poate sa le ia c si exista in v[n]

}


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

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

    for( a=1;a<=n;a++){
        for( b=1;b<=n;b++){
            if(a!=b){
                cautbin();
            }
        }
    }
    fout<<cont/6;
    return 0;
}