Cod sursa(job #2071419)

Utilizator vladisimovlad coneschi vladisimo Data 20 noiembrie 2017 17:43:28
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX_N = 800;
int n, k1, k2, sol, x[2 + MAX_N];
int verif(int m, int k1, int k2) {
  if (m + k1 < k2)
    return 0;
  if (m + k2 < k1)
    return 0;
  if (k1 + k2 < m)
    return 0;
  return 1;
}
void cb(int p, int u) {
  if (p <= u) {
    int m = (p + u) / 2;
    if (verif(x[m], k1, k2) == 1 && x[m] != k1 && x[m] != k2)
      sol++;
    cb(p , m - 1);
    cb(m + 1, u);
  }
}
int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> x[i];
  sort(x + 1, x + n + 1);
  int SOL = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      int k = 1;
      k1 = x[i];
      k2 = x[j];
      sol = 0;
      while (k <= n && x[k] < x[i] + x[j])
        k++;
      if (x[k] > x[i] + x[j])
        k--;
      cb(j + 1, k);
      if (sol)
        SOL += sol;
       // fout << x[i] << " " << x[j] << " " << x[sol] << '\n';
    }
  fout << SOL;
  return 0;
}