Cod sursa(job #1782809)

Utilizator oana.durcauOana Durcau oana.durcau Data 18 octombrie 2016 16:15:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int x[1000],N, i, j, poz, nrtri, sum;
void citire()
{
    fin>>N;
    for(i=1; i<=N; i++)
        fin>>x[i];
}
int caut_bin(int a, int st, int dr)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x[mij]>a)
            dr=mij-1;
        else
            st=mij+1;

    }
    return dr;
}
int main()
{
    citire();
    sort(x+1,x+N+1);
    for(i=1; i<N-1; i++)
        for(j=i+1; j<=N-1; j++)
         {
             sum=x[i]+x[j];
             poz=caut_bin(sum, j+1,N);
            nrtri=nrtri+(poz-j);

         }
    fout<<nrtri;
    return 0;
}