Cod sursa(job #2003040)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 iulie 2017 16:03:08
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int val[801];
int n;
int pozInser;

void citire(){
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> val[i];
}

void QuickSort(int st, int dr){
  int i = st, j = dr;
  int pivot = val[(st + dr) / 2];
  while(i <= j){
    while(val[i] < pivot)i++;
    while(val[j] > pivot)j--;
    if(i <= j ){
      int aux = val[i];
      val[i] = val[j];
      val[j] = aux;
      i++;
      j--;
    }
  }
  if(i < dr)
    QuickSort(i, dr);
  if(j > st)
    QuickSort(st, j);
}

bool verificare(int i, int j,int mij){
  if(mij != i && mij != j)
    return true;
  return false;
}

int cautareBinara(int st, int dr, int caut, int i, int j){
  if(st > dr)
    return -1;
  else{
    int mij = (st + dr) / 2;
    if(val[mij] <= caut && (val[mij + 1] > caut || mij == n))
        return mij;
    else if(val[mij] <= caut && val[mij + 1] <= caut)
        st = mij + 1;
    else
        dr = mij - 1;
    cautareBinara(st, dr, caut, i , j);
  }
}

int main(){
  int nr = 0;
  citire();
  QuickSort(1, n);
  for(int i = 1; i < n ; i++)
    for(int j = i + 1; j <= n; j++){
      int sum = val[i] + val[j];
      int poz = cautareBinara(1,n, sum, i, j);
      if(poz != -1){
        while(poz > 0 && val[poz] + val[i] >=val[j] && val[poz] + val[j] > val[i]){
          if(verificare(i, j, poz) == true){
            //out << val[i] << ' '<< val[j] << ' '<< val[poz]<<'\n';
            nr ++;
          }
          poz--;
        }
      }
    }
  out << nr / 3;
  return 0;
}