Cod sursa(job #698302)

Utilizator alexamiu2008Miu Alexandra alexamiu2008 Data 29 februarie 2012 13:20:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
#include<stdlib.h>
FILE*fin,*fout;
int v[801],i,j,n,s[801],k,nr;
int cmp(const void*a,const void*b){
 return *(int*)a-*(int*)b;
}
int caut(int s,int p,int u){
u=n;   p=1;
int m,k,nr=0;
while(p<=u){
m=(p+u)/2;
if(v[m]>s){u=m-1;}
else{nr++;p=m+1;k=m;}

}

return k;
}



int main(){
fin=fopen("nrtri.in","r");
fout=fopen("nrtri.out","w");
fscanf(fin,"%d ",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%d",&v[i]);
}
qsort(v+1,n,sizeof(int),cmp);
for(i=1;i<n-1;i++){
for(j=i+1;j<n;j++){
  nr=nr+ caut(v[i]+v[j],j,n)-j;
}
}

fprintf(fout,"%d",nr);
return 0;
}