Cod sursa(job #2288785)

Utilizator BotzkiBotzki Botzki Data 23 noiembrie 2018 21:23:48
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
const int NMAX= 800;
int n;
int v[NMAX+5];
int cautare_binara(int st, int s)
{
   int dr=n, m;
   while(st<=dr)
   {
       m=(st+dr)/2;
       if(v[m]<=s)
           st=m+1;
       else
           dr=m-1;
   }
   return dr;
}
int main()
{
    int nrt=0, i, j, s;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    sort(v+1, v+n+1);
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            s=v[i]+v[j];
            nrt=nrt+cautare_binara(j+1, s)-j;

        }
    }
    fout<<nrt<<"\n";
    return 0;
}