Cod sursa(job #2123564)

Utilizator Iulia14iulia slanina Iulia14 Data 6 februarie 2018 13:10:27
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("nrtri.in");
ofstream cout ("nrtri.out");
short int v[805];

int main()
{
    int n,i,s=0,j,x1,x2,m,st,dr,nr=0;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
//        vc[v[i]]++;
    }
    sort(v+1,v+n+1);
    for (i=1;i<=n;i++)
    {
        for (j=i+1;j<=n;j++)
        {
            st=1;
            dr=n;
            s=v[i]+v[j];
            x2=0;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]<=s)
                {
                    x2=m;
                    st=m+1;
                }
                else
                dr=m-1;
            }
            st=1;
            dr=x2;
            if (x2!=0)
            {
                x1=0;
                s=max(v[i],v[j])-min(v[i],v[j]);
                st=1;
                dr=x2;
                while (st<=dr)
                {
                    m=(st+dr)/2;
                    if (s<=v[m])
                    {
                        x1=m;
                        dr=m-1;
                    }
                    else
                    st=m+1;
                }
                if (x1!=0)
                {
                    nr+=(x2-x1+1);
                    if (v[i]*2>=v[j])
                        nr--;
                    if (v[j]*2>=v[i])
                        nr--;
                }
            }

        }
    }
    cout<<nr/3;
    return 0;
}