Cod sursa(job #895923)

Utilizator George515600Bejan George George515600 Data 27 februarie 2013 13:04:48
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.58 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 cauta(int v[], int poz, int start, int finish)//cea mai mare pozitie pt care v[a]+v[b]>=v[med]
{
    int med=(start+finish)/2;
    while (start<=finish){
      if (poz>=v[med]&& v[med+1]>poz) return med;
     else
     if (poz>=v[med]){
        start=med+1;
        med=(start+finish)/2;
     }else{
     finish=med-1;
     med=(start+finish)/2;
     }
    }
    return -1;
}

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

    int v[MAX];
    int n,i;

    scanf("%d", &n);

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

    quicksort(v,1,n);
    i = 0;
    int nr = 0;
    for (int a=0;a<=n-3;a++)
    for (int b=a+1;b<=n-2;b++){
        int start=b+1;
        int final1=n ;
       int c=cauta(v, v[a]+v[b],start,final1);
        if (c>b){
            int aux=c-b;
            nr+=aux;
        }
    }


    printf("%d", nr);

    return 0;


}