Cod sursa(job #2696086)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 15 ianuarie 2021 12:15:07
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;


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

int lungimi[805];



int binarySearch(int left, int right, int val)
{
  int bestVal = -1;

  while(left <= right)
  {
    int mid = (left + right) / 2;
    //cout << mid << ' ';
    if(lungimi[mid] <= val)
    {
      bestVal = mid;
      left = mid + 1;
    }
    else
    {
      right = mid - 1;
    }
  }
  //cout << '\n';
  return bestVal;

}



int main() 
{
  int n;
  fin >> n;

  for(int i = 0; i < n; i++)
  {
    fin >> lungimi[i];
  }

  sort(lungimi + 0, lungimi + n);

  int cazuri = 0;

  for(int i = 0; i < n; i++)
  {
    for(int j = i + 1; j < n; j++)
    {
      int a = lungimi[i];
      int b = lungimi[j];

      int searchVal = a + b;
      //cout << binarySearch(j + 1, n - 1, searchVal)<< ' ';

      int valBin = binarySearch(j + 1, n - 1, searchVal);
      if (valBin > -1)
      {
         cazuri += valBin - j;
      }
     
      
    }
  }

  fout << cazuri;

}