Cod sursa(job #2009193)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 8 august 2017 21:29:45
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>

const int MAXN = 8e2;

int v[MAXN + 1];

int main() {
  int n, st, dr, s, m, cnt;
  FILE *f = fopen("nrtri.in", "r");
  fscanf(f, "%d", &n);
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d", &v[i]);
  }
  fclose(f);
  std::sort(v, v + n);
  cnt = 0;
  for (int i = 0; i < n - 2; ++i) {
    for (int j = i + 1; j < n - 1; ++j) {
      s = v[i] + v[j];
      st = j + 1;
      dr = n - 1;
      while (st < dr) {
        m = (st + dr) >> 1;
        if (v[m] < s) {
          st = m + 1;
        } else {
          dr = m - 1;
        }
      }
      if (s >= v[dr]) {
        ++dr;
      }
      cnt += dr - j - 1;
    }
  }
  f = fopen("nrtri.out", "w");
  fprintf(f, "%d\n", cnt);
  fclose(f);
  return 0;
}