Cod sursa(job #1771709)

Utilizator andra1782Andra Alazaroaie andra1782 Data 5 octombrie 2016 21:55:06
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
int v[800];

void quicksort(int p, int u){
    int pivot,i,j,aux;

    pivot=v[(p+u)/2];
    i=p;
    j=u;
    while(i<=j){
        while(i<u && v[i]<pivot)
            i++;
        while(j>p && v[j]>pivot)
            j--;
        if(i<=j){
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
    }
    if(j>p)
        quicksort(p,j);
    if(i<u)
        quicksort(i,u);
}

int main(){
    FILE *fin=fopen("nrtri.in","r");
    FILE *fout=fopen("nrtri.out","w");
    int n,i,j,sol=0,k,pas;

    fscanf(fin,"%d",&n);
    for(i=0; i<n; i++)
        fscanf(fin,"%d",&v[i]);
    quicksort(0,n-1);
    for(i=0; i<n-2; i++)
        for(j=i+1; j<n-1; j++){
            k=j+1;
            pas=1<<10;
            while(pas!=0){
                if(k+pas<n && v[k+pas]<=v[i]+v[j])
                    k+=pas;
                pas/=2;
            }
            if(v[k]<=v[i]+v[j])
                sol+=k-j;
        }
    fprintf(fout,"%d\n",sol);
    fclose(fin);
    fclose(fout);
    return 0;
}