Cod sursa(job #1085963)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 17 ianuarie 2014 16:34:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int N,v[1000];

inline int BSearch1(int x)
{
    int st,dr,mij;
    st=1; dr=N;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=(st+dr)/2;
    if(v[mij]>x || mij>N)
        --mij;
    return mij;
}

inline int BSearch2(int x)
{
    int st,dr,mij;
    st=1; dr=N;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
            dr=mij-1;
        else
            st=mij+1;
    }
    mij=(st+dr)/2;
    if(v[mij]<x || !mij)
        ++mij;
    return mij;
}

int main()
{
    int i,j,k,sol=0,poz1,poz2;
    freopen ("nrtri.in","r",stdin);
    freopen ("nrtri.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%d", &v[i]);
    sort(v+1,v+N+1);
    for(i=1;i<N;++i)
        for(j=i+1;j<=N;++j)
        {
            poz1=BSearch1(v[i]+v[j]);
            poz2=BSearch2(max(v[i]-v[j],v[j]-v[i]));
            sol+=(poz1-poz2+1);
            if(poz2<=i && i<=poz1)
                --sol;
            if(poz2<=j && j<=poz1)
                --sol;
        }
    sol/=3;
    printf("%d\n", sol);
    return 0;
}