Cod sursa(job #2081246)

Utilizator SmitOanea Smit Andrei Smit Data 4 decembrie 2017 14:50:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

int n,sol;
int a[803];

int CautBin(int st,int dr,int x)
{
    int stg,drp,mijl,poz;
    stg=st;
    drp=dr;
    poz=-1;
    while(stg<=drp)
    {
        mijl=(stg+drp)/2;
        if(a[mijl]<=x)
        {
            poz=mijl;
            stg=mijl+1;
        }
        else
            drp=mijl-1;
    }
    return poz;
}

int main()
{
    int i,j,l1,l2,l3,poz;
    ///citire
    ifstream fin("nrtri.in");
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    fin.close();

    ///solutie
    sort(a+1,a+n+1);
    for(i=1;i<n;++i)
    {
        //cout<<i<<"\n";
        l1=a[i];
        for(j=i+1;j<=n;++j)
        {
            l2=a[j];
            poz=CautBin(j+1,n,l1+l2);
            //cout<<"\t"<<j<<"\n";
            if(poz!=-1)
            {
                sol+=(poz-j);
                //cout<<"\t\t"<<poz<<"\n";
            }
        }
    }

    ///afisare
    ofstream fout("nrtri.out");
    fout<<sol<<"\n";
    //cout<<sol<<"\n";
    fout.close();
    return 0;
}