Cod sursa(job #2295241)

Utilizator cameliapatileaPatilea Catalina Camelia cameliapatilea Data 3 decembrie 2018 13:39:40
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");


vector <int> v;
int cautare_binara(int l, int r, int x)
{
    int mijloc;
//cat timp cele doua capete nu s-au depasit
    while(l < r)
    {
        mijloc = ( l + r) / 2;

        if( v[mijloc] <= x)
            l = mijloc + 1;
        else r = mijloc ;
    }
    mijloc = ( l + r) / 2;
    if( v[mijloc] > x)
        //daca elementul cautat este mai mic decat v[mijloc], scad mijlocul
        mijloc --;
    return mijloc;
}
int main() {
    int n, i, x;
    int suma, k, nr=0;
    f>>n;

    for(i = 1; i <= n; i++)
    {
        f >> x;
    v.push_back(x);
    }
    //sortez crescator
    sort(v.begin(), v.end());
  for(i = 0; i<= n - 2; i++)
  {
      for(int j = i+1; j <= n - 1; j++)
      {
          suma = v[i] + v[j];
          k = cautare_binara(j+1, n-1, suma);
          //adaug la fostul nr rezutatul returnat de functia catutare-binara si scad pozitia pe care ma aflu
          nr = nr + k - j ;

      }
  }
  g << nr;
  return 0;
}