Cod sursa(job #1789444)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 octombrie 2016 00:15:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("nrtri.in");
ofstream g ("nrtri.out");
int x[1000],N, i, j, poz, nrtri, sum;
void citire()
{
    f>>N;
    for(i=1; i<=N; i++)
        f>>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);

         }
    g<<nrtri;
    return 0;
}