Cod sursa(job #614166)

Utilizator AndreeaNNedelcu Andreea AndreeaN Data 5 octombrie 2011 19:43:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<stdlib.h>
FILE *f=fopen("nrtri.in","r"),*g=fopen("nrtri.out","w");
long int n,v[805];

void citire(){
long int i;
    fscanf(f,"%ld\n",&n);
    for(i=1; i<=n; i++){
        fscanf(f,"%ld",&v[i]);
    }
}

int cmp(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

void rezolva(){
long int i,j,st,dr,nr,nr_sol=0,mij;
    for(i=1; i<n; i++){
        for(j=i+1; j<=n; j++){
            st=j+1;dr=n;
            while (st<=dr) {
                mij=(st+dr)/2;
                if (v[mij]<=v[i]+v[j]) {st=mij+1;}
                else{dr=mij-1;}
            }
            if (v[mij]<=v[i]+v[j]){nr=mij;}
            else{nr=mij-1;}
            nr_sol=nr_sol+nr-j;

        }
    }
    fprintf(g,"%ld",nr_sol);
}


int main(){
    citire();
    qsort(v+1,n,sizeof(int),cmp);
    //for(long i=1; i<=n; i++){fprintf(g,"%ld\n",v[i]);}
    rezolva();
return 0;
}