Cod sursa(job #628313)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 1 noiembrie 2011 00:44:01
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define MAXN 800

#define MODUL(a) ((a) < 0 ? (-(a)) : (a))

int v[MAXN], n;

using namespace std;

int findge(int key, int li, int lf) {
  // imposibil
  if (li > lf) {
    return -1;
  }
  // ar trebui sa fie in dreapta
  if (v[lf] < key) {
    return -1;
  }
  // toate sunt bune
  if (v[li] >= key) {
    return li;
  }

  int m = (li + lf) / 2;
  if (v[m] < key) {
    return findge(key, m + 1, lf);
  } else {
    // Posibil asta, dar cauta si dincolo.
    int candidate = findge(key, li, m - 1);
    return candidate == -1 ? m : candidate;
  }
}

int findle(int key, int li, int lf) {
  // imposibil
  if (li > lf) {
    return -1;
  }
  // ar trebui sa fie in stanga
  if (v[li] > key) {
    return -1;
  }
  // toate sunt bune
  if (v[lf] <= key) {
    return lf;
  }

  int m = (li + lf) / 2;
  if (v[m] > key) {
    return findle(key, li, m - 1);
  } else {
    // Posibil asta, dar cauta si in partea cealalta
    int candidate = findle(key, m + 1, lf);
    return candidate == -1 ? m : candidate;
  }
}

int main()
{
  ifstream in("nrtri.in");
  ofstream out("nrtri.out");

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

  std::sort(v, v + n);

  int sol = 0;

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (i != j) {
        int plow = findge(v[j] - v[i], j + 1, n - 1);
        int phigh = findle(v[i] + v[j], j + 1, n - 1);
        if (plow != -1 && phigh != -1) {
          sol += phigh - plow + 1;
        }
      }
    }
  }

  out << sol << "\n";

  in.close();
  out.close();

  return 0;
}