Cod sursa(job #895884)

Utilizator George515600Bejan George George515600 Data 27 februarie 2013 12:56:01
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX 800

void quicksort(int x[],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

int caut(int v[], int lo, int hi, int val)
{
    int mid;

    while (lo <= hi)
    {
        mid = lo + (hi - lo)/2;
        if (val >= v[mid] && val < v[mid+1]) return mid;
        else
        if (v[mid] > val)
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    return 0;
}

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

    int v[MAX];
    int n,i, a, b, k,sum;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d ", &v[i]);

    quicksort(v,1,n);
    i = 0;
    for (a = 0; a < n-2; a++)
        for (b = a+1; b < n-1; b++)
        {
            sum = v[a] + v[b];
            k = caut(v,b+1, n-1, sum);
            if (k > b)
                i += k - b;

        }


    printf("%d", i);

    return 0;


}