Cod sursa(job #2405781)

Utilizator HelloWorldBogdan Rizescu HelloWorld Data 14 aprilie 2019 21:32:45
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n,i,j,triunghiuri,mij,st,dr,a[801];
int main()
{
    in>>n;
    for (i=1; i<=n; ++i)
    {
        in>>a[i];
    }
    sort(a+1,a+n+1);
    for (i=1; i<=n; ++i)
    {
        for (j=i+1; j<n; ++j)
        {
            st=j+1;
            dr=n;
            mij=0;
            while (st<dr)
            {
                mij=(st+dr+1)/2;
                if (a[i]+a[j]>=a[mij] && a[i]+a[mij]>=a[j] && a[j]+a[mij]>=a[i])
                    st=mij;
                else
                    dr=mij-1;
            }
            if (a[i]+a[j]>=a[st] && a[i]+a[st]>=a[j] && a[j]+a[st]>=a[i] && st!=i && st!=j)
                triunghiuri+=(st-j);
        }
    }
    out<<triunghiuri<<"\n";
}