Cod sursa(job #1960830)

Utilizator PetyAlexandru Peticaru Pety Data 10 aprilie 2017 18:26:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb

/// arta tata

#include <fstream>
#include <algorithm>
using namespace std;

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


int main()
{

    int n,st,dr,mij,v[800],s=0,x,sol;
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>v[i];
    sort(v,v+n);
    for(int i=0;i<n-2;i++)
        for(int j=i+1;j<n-1;j++)
    {
        x=v[i]+v[j];
        st=j+1;
        dr=n-1;
        sol=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]<=x)
            {
                sol=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        if(sol!=0)
            s+=sol-j;

    }
    fout<<s;

    return 0;
}