Cod sursa(job #2023303)

Utilizator Vladi.BarasBaras Nicholas Vladimir Laurentiu Vladi.Baras Data 18 septembrie 2017 18:36:17
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int NMAX=800;
int v[NMAX+1];
int n;
bool triunghi(int a1, int a2, int a3)
{
    if(a3<=a2+a1)
        return 1;
    return 0;
}
int cautareBinara(int k,int i, int j)
{
    int st =k,dr=n,mid;
    int maxim=0;
    while(st<=dr)
    {
        mid=st+dr,mid/=2;
        if(triunghi(v[i],v[j],v[mid])==1)
        {
            maxim=mid;
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    return maxim;

}
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);

    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&v[i]);
    }
    sort(v+1,v+n+1);
    int s=0;
    for(int i=1; i<=n-2; i++)
    {
        for(int j=i+1; j<=n-1; ++j)
        {
            int tmp = cautareBinara(j+1,i,j);
            //cout<<i<<' '<<j<<' '<<tmp<<endl;
            if(tmp != 0)
                s+=tmp-j;
        }
    }
    printf("%d\n",s);
    return 0;
}