Cod sursa(job #739387)

Utilizator Athena99Anghel Anca Athena99 Data 22 aprilie 2012 21:45:18
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>

int v[810];

int bs(int i, int j,int n)
{
    int start=j,stop=n-1,mid=0,a=j,b=n-1;
    mid=(start+stop)/2;
    while (v[mid]>v[i]+v[j] || (v[mid+1]<=v[i]+v[j] && mid+1<n))
    {
        if (v[mid]>v[i]+v[j])
        {
            stop=mid;
            if (stop==b)
                --stop;
        }
        if (v[mid+1]<=v[i]+v[j])
        {
            start=mid;
            if (start==a)
                ++start;
        }
        a=start;
        b=stop;
        mid=(start+stop)/2;
    }
    return mid;
}

int main()
{
    int i=0,n=0,j=0,k=0,s=0,min=0,aux=0,poz=0;
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d",&n);
    for (i=0; i<n; ++i)
        scanf("%d",&v[i]);
    for (i=0; i<n; ++i)
    {
        aux=v[i];
        min=v[i];
        poz=i;
        for (j=i+1; j<n; ++j)
            if (v[j]<min)
            {
                min=v[j];
                poz=j;
            }
        v[i]=min;
        v[poz]=aux;
    }
    for (i=0; i<n-2; ++i)
        for (j=i+1; j<n-1; ++j)
        {
            k=bs(i,j,n);
            s=s+k-j;
            k=0;
        }
    printf("%d",s);
    return 0;
}