Cod sursa(job #1329763)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 29 ianuarie 2015 20:26:13
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
int v[801];
void quicksort(int p,int u)
{
    int pivot,j,i,aux,t;
    if(p<u)
    {
        pivot=v[(p+u)/2];
        i=p;
        j=u;
        while(i<=j)
        {
            while(v[i]<pivot && i<u)
                i++;
            while(v[j]>pivot && j>p)
                j--;
            if(i<=j){
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
                i++;
                j--;
            }
        }
        if(p<j)
            quicksort(p,j);
        if(i<u)
            quicksort(i,u);
    }
}
int main()
{
    int n,i,sum,j,d,m,s;
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d",&v[i]);
    quicksort(1,n);
    sum=0;
    for(i=1; i<=n-2; i++)
        for(j=i+1; j<=n-1; j++)
        {
            s=j+1;
            d=n;
            while(d-s>1)
            {
                m=(s+d)/2;
                if(v[i]+v[j]<=v[m])
                    d=m-1;
                else
                    s=m+1;
            }
            while(d<=n && v[d]<=v[i]+v[j])
                d++;
            if(d<=n)
                sum++;
        }
    printf("%d\n",sum);

    return 0;
}