Cod sursa(job #2003015)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 iulie 2017 15:02:12
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int val[801];
int n;
int poz;

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 = (st + dr) / 2;
  while(i <= j){
    while(val[i] < val[pivot] && i < dr)i++;
    while(val[j] > val[pivot] && j > st)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);
}

void cautareBinara(int st, int dr, int caut){

  while(st <= dr){
    int mij = (st + dr) / 2;
    if(val[mij] <= caut){
      poz = mij;
      st = mij + 1;
    }
    else
      dr = mij - 1;
  }

}

int main(){
  int nr = 0;
  citire();
  QuickSort(1, n);
  for(int i = 1; i < n - 1 ; i++)
    for(int j = i + 1; j < n ; j++){
      int sum = val[i] + val[j];
      poz = 0;
      cautareBinara(j + 1, n, sum);
      if(poz != 0)
        nr += poz - j;
    }
  out << nr ;
  return 0;
}