Cod sursa(job #2296144)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 4 decembrie 2018 15:06:00
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> v;
int cautare_binara(int l,int r,int nr)
{
    int mij;
    while(l<r)
    {
        mij=(l+r)/2;
        if(v[mij]<=nr)
        {
            l=mij+1;//crestem l
        }
        else
        {
            r=mij;//scadem r
        }
    }
    mij=(l+r)/2;//mij devine mijlocul dintre l si r, echivalentul pivotului
    if(v[mij]>nr)//daca v[mij]>nr
    {
        mij--;//il scadem pe mij, pana ajungem la un element care sa convina
        //proprietatii de triunghi
    }
    return mij;
}
int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    int n,i,j,s_laturi,pos,nr,counter=0;
    fin>>n;//citim numarul de laturi
    for(i=0;i<=n-1;i++)
    {
        fin>>nr;//citim elementele
        v.push_back(nr);//le introducem in v prin push_back, ca sa isi pastreze ordinea
    }
    sort(v.begin(),v.end());//le sortam prin functia sort din STL
    for(i=0;i<=n-2;i++)
    {for(j=i+1;j<=n-1;j++)
      {
          s_laturi=v[i]+v[j];//punem in s_laturi suma a doua elemente v[i] si v[j]
          pos=cautare_binara(j+1,n-1,s_laturi);//il "cautam" pe al treilea element care sa corespunda
          //si care sa verifice proprietatea de triunghi
          counter=counter+pos-j;//in counter adunam pos, adica numarul de posibilitati pentru al treilea element din triplet
          //din caare scadem j,indicele elementului al doilea ca marime din triplet
      }
    }
    fout<<counter;
    fin.close();
    fout.close();
    return 0;
}