Cod sursa(job #2281089)

Utilizator cameliapatileaPatilea Catalina Camelia cameliapatilea Data 11 noiembrie 2018 16:06:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 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;

    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 mare decat v[mijloc], cresc 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);
    }
    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);
          nr = nr + k - j ;

      }
  }
  g << nr;
  return 0;
}