Cod sursa(job #2453927)

Utilizator TudorP2006Popescu Tudor TudorP2006 Data 6 septembrie 2019 16:05:27
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[800];
int cautare( int x, int st, int dr ){
  int mid;
  while ( st < dr ){
    mid = st + ( dr - st  ) / 2;
    if ( v[mid] <= x )
      st = mid + 1;
    else
      dr = mid;
  }
  return st - 1;
}
int main(){
  int n, i, j, poz, cnt;
  fin >> n;
  for ( i = 0; i < n; i++ )
    fin >> v[i];
  sort( v, v + n );
  cnt = 0;
  for ( i = 0; i < n - 1; i++ ){
    for ( j = i + 1; j < n; j++){
      cnt+= cautare( v[i] + v[j], j + 1, n ) - j;
    }
  }
  fout << cnt;
  return 0;
}