Cod sursa(job #2195597)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 16 aprilie 2018 20:02:58
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define nmax 801

using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int N,a[nmax],nrcomp,ok,maxim,maxim2,nr,d,ans;
int cautbinar(int st, int dr, int val)
{
      int mij;
      int rez=-2;
      while(st <= dr)
      {
          int mij=(st+dr)/2;
          if(val < a[mij])
            dr=mij-1;
          else if(val >= a[mij])
          {
              rez=mij;//calculez cea mai mare pozitie pe care se afla o valoare mai mica
              //sau egala cu numarul meu;
              st=mij+1;
          }
      }
      return rez;

    }
int main()
{
    fin>>N;
    for(int i =1; i <= N; i ++)
        fin>>a[i];
    sort(a+1,a+N+1);
    for(int i =1 ;i <= N- 2; i ++)
        for(int j = i + 1 ;j <= N-1 ; j++)
    {
         d=a[i]+a[j];
        nr=cautbinar(j+1,N,d);
        if(nr!=-2)//obtin un interval de valori bune de la nr la j;
            ans+=nr-j;
    }
    fout<<ans;

  return 0;
}