Cod sursa(job #1905256)

Utilizator herbertoHerbert Mohanu herberto Data 5 martie 2017 23:11:23
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000

int v[MAXN];
void myqsort(int begin, int end){
    int aux, b, e, pivot;
    b=begin;
    e=end;
    pivot=v[begin+rand()%(end-begin+1)];
    while(b<=e){
        while(v[b]<pivot)
            b++;
        while(v[e]>pivot)
            e--;
        if(b<=e){
            aux=v[b];
            v[b]=v[e];
            v[e]=aux;
            b++;
            e--;
        }
    }
    if(begin<e)
        myqsort(begin, e);
    if(b<end)
        myqsort(b, end);
}
int main(){
    FILE*fin=fopen("nrtri.in", "r");
    FILE*fout=fopen("nrtri.out", "w");
    int n, i, j, p, t;
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++)
        fscanf(fin, "%d", &v[i]);

    myqsort(0, n-1);
    t=0;
    for(i=0; i<n-2; i++){
        p=i+2;
        for(j=i+1; j<n-1; j++){
            if(p==j)
                p++;
            while(p<n && v[i]+v[j]>=v[p])
                p++;

            t=t+p-j-1;
        }
    }
    fprintf(fout, "%d", t);
    return 0;
}