Cod sursa(job #912870)

Utilizator doomaSalagean Calin dooma Data 12 martie 2013 21:40:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream>
#include<algorithm>
using namespace std;
int N, a[801];
int cautare_binara(int lo, int c){
    int hi = N, mid;
    while(hi - lo > 1){
        mid = lo+(hi - lo)/2;
        if(a[mid] < c) lo = mid;
        else hi = mid;
    }
    return hi;
}
int main(){
  ifstream fin("nrtri.in");
  ofstream fout("nrtri.out");
  int i,j, t, s = 0;
  fin >> N;
  for(i = 0; i < N; i++) fin >> a[i];
  sort(a, a+N);
  for(i = 0; i < N-2; i++){
    for(j = i+1; j < N-1; j++){
        t = cautare_binara(j, a[i] + a[j] + 1);
        s+=t-j-1;
    }
  }
  fout << s << "\n";
  fin.close();
  fout.close();
  return 0;
}