Cod sursa(job #2032162)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 4 octombrie 2017 17:31:38
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, v[800];
int lat1, lat2;
int pas = 1, indice, cnt, poz;

int main (){
  in >> n;

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

  sort(v, v + n);

  for (int i = 0; i < n - 1; ++ i){
    lat1 = v[i];
    lat2 = v[i + 1];

    poz = 0;
    for (pas = 1; pas < n - 1; pas <<= 1);

    while (pas > 0){
      indice = poz + pas;

      if (indice < n && v[indice] < lat1 + lat2 && (indice > i + 1 || indice < i))
        poz = indice;

      pas = pas >> 1;
    }

    if (poz != 0){
      if (poz < i)
        cnt += i - poz;
      if (poz > i + 1)
        cnt += poz - (i + 1);
    }
  }

  out << cnt;

  return 0;
}