Pagini recente » Cod sursa (job #2792437) | Cod sursa (job #2246888) | Cod sursa (job #1953981) | Cod sursa (job #3131807) | Cod sursa (job #209088)
Cod sursa(job #209088)
#include <cstdio>
#include <cstdlib>
int nr,i1,i2,i3,n,v[850],p;
int comp(const void *a, const void *b){
int aa=*(int*)a,bb=*(int*)b;
if (aa>bb)
return 1;
if (aa<bb)
return -1;
return 0;
}
void read(){
int i;
freopen("nrtri.in","r",stdin);
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%d",&v[i]);
qsort(v,n+1,sizeof(v[0]),comp);
}
int bsearch(int p,int u){
int m;
while(p!=u){
m=(p+u)/2;
if (v[i1]+v[i2]<=v[m])
u=m;
else
p=m+1;
}
if(v[p]>v[i1]+v[i2])
--p;
return p;
}
void solve(){
for (i1=1;i1<=n-2;++i1)
for (i2=i1+1;i2<=n-1;++i2){
p=bsearch(i2+1,n);
/*
for(int i=i2+1;i<=p;++i)
printf("(%d,%d,%d)\n",v[i1],v[i2],v[i]);
*/
nr+=(p-i2);
}
}
void write(){
freopen("nrtri.out","w",stdout);
printf("%d\n",nr);
}
int main(){
read();
solve();
write();
}